[2110] 공유기 설치

2110번: 공유기 설치

 

이분탐색 문제다.

 

공유기를 설치할 때 간격이 최대한 넓어야 한다. 처음엔 c만큼 조합을 구해야 할까 고민했는데 N의 최대 크기가 10^5라 시간초과가 날 것이다. 이렇게 데이터가 많은 경우 이분탐색으로 생각해보야 한다. 공유기 간격이 최대면서 동시에 공유기 개수가 맞아야 하므로 공유기 간격의 범위를 비교해가며 공유기가 설치될 자리를 찍어보며 공유기 간격을 조절하는 것이 핵심이겠다.

 

특히 간격이 middle일 때 공유기를 설치할 수 있는 개수를 구하는 것이 핵심인데, 나는 설치할 수 없을 경우 interval로 해당 공유기의 좌표를 담고 설치할 수 있는 경우 interval을 0으로 두고 개수를 늘려주었다. 이렇게 하면 설치할 수 있는 자리(설치된 공유기와의 간격이 middle보다 큰 경우)에 모두 공유기를 설치할 수 있게 된다. 이때 C만큼 설치하는 것이 아니라 설치할 수 있는 개수를 구해주는 것이 관건이다. 왜냐하면 간격을 이분탐색하고 있기 때문에 최대로 많이 설치되는 경우가 C보다 큰지 작은지 확인하며 범위를 줄여나가줘야하기 때문이다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int N, C;
    int data[200001];
    
    cin >> N >> C;
    
    for(int i = 0; i < N; i++)
        cin >> data[i];
    
    sort(data, data + N);
        
    int start = 1;
    int end = data[N - 1] - data[0];
    
    while(start <= end){
        int middle = (start + end) / 2;
        
        int cnt = 1;
        int interval = 0;
        
        for(int i = 0; i < N - 1; i++){
            if(interval + data[i + 1] - data[i] >= middle){
                cnt += 1;
                interval = 0;
            } else
                interval += (data[i + 1] - data[i]);
        }
        
        if(cnt >= C) start = middle + 1;
        else end = middle - 1;
    }
    
    cout << end;

    return 0;
}