[1일 1알고] G4 2110 공유기 설치

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

 

N개의 집이 있고 공유기 C개를 설치해야합니다.

집의 좌표가 최대 10억이고, 집의 개수가 20만 이하이기 때문에 브루트 포스 식 탐색을 하는 문제는 아닐 것입니다.

 

한 집에는 하나의 공유기만 설치 가능하며, 가장 인접한 공유기의 설치거리가 최대가 되는 방법이 답이 됩니다.

---

 문제는 특정 간격 d만큼이 답이라고 가정했을 때 공유기 C개를 설치할 수 있는가? 의 물음을 이진 탐색을 통해 찾아갑니다.

만약 d로 가정했을 때 C개를 모두 설치할 수 있었따면 d의 값을 늘려보고, 설치할 수 없었다면 d의 값을 줄여봅니다.

 

중요한 점은 이진 탐색을 할 때 기준이 이 "간격"이라는 것입니다. left = 최소 간격 = 1이 되고, (집의 위치가 모두 다르기 때문에) right = 최대 간격 = 정렬 시 최댓값과 최소값의 차이 가 됩니다.

 

이 left와 right를 통해 d를 설정하고 d간격일 때 조건에 만족하는지를 반복하며 확인합니다. 

 

bool isValid(vector<long long>& v, int val);
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> C;

    vector<long long> v(N, 0);

    for (int i = 0; i < N; ++i)
    {
        cin >> v[i];
    }

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

    int left = 1;
    int right = v[N - 1] - v[0];
    int result = -1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (isValid(v, mid))
        {
            result = mid;
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    cout << result;
    return 0;
}

bool isValid(vector<long long>& v, int val)
{
    int cnt = 1;
    int last = v[0];
    for (int i = 1; i < N; ++i)
    {
        if (v[i] - last >= val)
        {
            ++cnt;
            last = v[i];
        }
    }

    return cnt >= C;
}

 

이번 문제는 이진 탐색의 조건을 생각하지 못해 애를 먹었네요