[boj] 백준 2110 공유기 설치 - 이분탐색

[문제]

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

2110번: 공유기 설치

 

[풀이]

문제를 이해 못해서 당황했으나... 가장 인접한 두 공유기 사이의 거리가 최대가 되게하라는 것은 결국 c개의 공유기를 적절한 거리를 두고 설치할건데, c개의 공유기를 설치할 때의 공유기가 설치된 집들 간 거리 중 최소 거리(가장 인접한)가 최대가 될 때의 거리를 출력하라는 것이다. 

오랜만에 푸는 이분탐색 문제이다. 먼저 공유기가 설치된 집들 간 최소거리는 1이고, 최대 거리는 끝집과 첫집의 거리이다. 이 거리를 기준으로 이분탐색을 진행한다. 이전에 설치된 집과 그 다음 집과의 거리가 기준 거리인 mid와 같거나 더 크면, 설치 가능함을 의미한다. 따라서 cnt를 증가해주고 공유기가 설치된 집의 위치를 갱신해준다. 모든 집에 대해 반복문을 돈 후, 설치 가능한 공유기 개수인 cnt가 c보다 작다는 것은 간격을 좁혀 더 많이 설치할 필요가 있다는 것이다. 따라서 right = mid -1 로 갱신해서 기준 거리를 줄여 다시 계산하도록 한다. 반대인 경우 간격을 넓혀 더 적게 설치해야 한다는 뜻이므로 left = mid + 1로 갱신해준다. 

 

참고) 문제의 매커니즘은 다음 게시글을 참고하면 좋다.

 

[코드]

 

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, c;

    cin >> n >> c;

    vector<int> house(n);
    for (int i=0; i < n; i++)
        cin >> house[i];

    sort(house.begin(), house.end()); //이분 탐색은 정렬 후 진행! 

    int left = 1, right = house[n-1]-house[0]; //공유기 간격의 최소 거리, 최대 거리

    while (left <= right) {
        int cnt = 1;
        int loc = 0;
        int mid = (left + right) / 2;

        for (int i = 1; i < n; i++) {
            if (house[i] - house[loc] >= mid) { //이전에 공유기가 설치된 집과 다음 집의 간격이 기준 거리보다 같거나 크면 공유기 설치 가능
                loc = i; //공유기가 설치된 마지막 집 위치 갱신
                cnt++;
            }
        }
        if (cnt < c)
            right = mid - 1; //기준거리를 좁혀서 더 많이 설치할 필요 있음.
        else
            left = mid + 1; //기준거리를 늘여서 더 적게 설치할 필요 있음.

    }
    
    cout << right;
}