[1477] 주유소 세우기

 

1477번: 휴게소 세우기

 

이분 탐색 문제다

 

기존에 세워진 N개의 주유소에 M개의 주유소를 더할 때 인접한 두 주유소의 최대 값이 최소가 되게 하는 문제다. 발상은 쉬웠으나 디테일에서 굉장히 헛다리를 많이 짚었다. 

 

인접한 두 주유소의 거리가 최소가 되게 한다는 점에서, 주어진 주유소는 이미 세워졌으므로 현재 인접한 주유소의 간격이 가장 넓은 경우보다 더 크지는 않겠다는 생각으로 주유소 사이의 거리의 최대값을 구했다. 

그리고 주유소의 거리의 최대 값의 최소가 되려면 간격은 물론 일정해야 한다. 그렇기 떄문에 이미 세워진 각각의 주유소 간격에 이분탐색의 middle을 나눈 몫으로 해당 간격에 세워질 수 있는 주유소의 개수를 구하는 것이 이 문제의 중심이겠다.

 

하지만 나는 양 끝에 주유소가 세워질 수 없으므로 주유소가 세워진 셈 칠 수 있다는 점, 그리고 이미 세워진 주유소 위에는 주유소가 세워질 수 있다는 점을 간과하여 답이 나오지 않았지만, 그 두 가지 부분을 고쳤음에도 불구하고 답이 나오지 않는 상황에 맞닦들였다. 아직 이유를 모르겠다. 다른 사람들의 코드와 다른 점은 나는 vector가 아닌 배열로 풀었다는 점이 전부다......... 문제를 해결하게 된다면 글을 다시 수정하겠다. ㅠㅠ

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    int N, M, L;

    cin >> N >> M >> L;

    vector<int> data;

    data.push_back(0);

    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        data.push_back(a);
    }

    data.push_back(L);

    sort(data.begin(), data.end());

    int start = 1;
    int end = L - 1;

    while (start <= end) {
        int middle = (start + end) / 2;

        int cnt = 0;

        for (int i = 1; i < data.size(); i++) {
            int dist = data[i] - data[i - 1];
            cnt += dist / middle;

            if (dist % middle == 0) cnt -= 1;
        }

        if (cnt > M) start = middle + 1;
        else end = middle - 1;
    }

    cout << end + 1;

    return 0;
}