[백준] 6209번 제자리 멀리뛰기 (C++)

https://www.acmicpc.net/problem/6209

 

 

이 문제는 현재 돌섬에서 탈출구까지의 거리와 돌섬의 수, 제거할 수 있는 돌섬의 수가 주어지고 N개의 줄에 돌섬이 어디에 위치해 있는지 주어질때 각 돌섬을 넘어 탈출구로 탈출할때 점프할 수 있는 최소거리의 최댓값을 출력해야한다.

 

말로 들었을때 이해가 잘 안될 수 있으므로 그림으로 한번 봐보자

 

 

각각의 돌섬의 거리에서 최소 거리를 알아내고 그 최소거리를 최대로 만들기 위해 M개의 돌섬을 제거해야한다.

 

이때 돌섬까지의 거리는 10억이며 돌섬의 개수는 5만이다 나는 최소거리를 구하기 위해서 그 값을 x로 두고

탐색을 진행하여 만약 최소거리보다 더 작게 나오는 경우 이는 돌섬을 제거해야하기 때문에 개수를 증가시켜주었고

돌섬을 제거하는 개수가 M개보다 클 경우 이는 최소거리가 더 작아야하기 때문에 right값을 줄여주는 방식을 사용하였다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int d, n, m, answer;

void solve(vector<int> &v) {
    sort(v.begin(), v.end());

    int left = 0;
    int right = d;

    while(left <= right) {
        int mid = (left + right) / 2;

        int stone = 0;
        int locate = 0;
        int min_dist = d;
        for(int i = 0; i < n; i++) {
            if(v[i] - locate >= mid) {
                min_dist = min(min_dist, v[i] - locate);
                locate = v[i];
            }
            else stone++;
        }

        min_dist = min(min_dist, d - locate);

        if(stone > m) {     // 돌 제거를 m보다 많이 한 경우 점프할 수 있는 mid값을 줄여야함
            right = mid - 1;
        }
        else {
            answer = max(answer, mid);
            left = mid + 1;
        }
    }

    cout << answer;
}

void input() {
    cin >> d >> n >> m;

    vector<int> v(n, 0);

    for(auto &it : v) {
        cin >> it;
    }

    solve(v);
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
}