[C++/백준 2110] 공유기 설치

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


int home[200001];
int ans = 0;

void binary_search(int n, int c){
    
    int l = 0;
    int r = home[n-1] - home[0];
    
    while(1){
        if(l > r){
            return;
        }
        
        int mid = (l + r) / 2;
        // 거리를 mid 이상으로 해서 몇개의 공유기를 설치할 수 있는가?
        int count = 1;
        
        int compare = home[0];
        for(int i = 1 ; i < n ; i ++){
            if(home[i] - compare >= mid){
                count++;
                compare = home[i];
            }   
        }
        
        if(count < c){ //설치할 수 없다. 거리를 줄이자.
            r = mid - 1;
        }else{ //설치할 수 있다. 거리를 늘린다.
            l = mid + 1;
            ans = max(ans, mid);
        }   
    }
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, c;
    cin >> n >> c;
    
    for(int i = 0 ; i < n ; i++){
        cin >> home[i];
    }
    sort(home, home + n);
    
    binary_search(n, c);
   
    cout << ans;
    
    return 0;
}

 

이분 탐색 중 parametric search 문제이다.

 

집 좌표 범위  (0 ≤ xi ≤ 1,000,000,000) 를 보고 시간초과가 관건이겠군 하고 이분 탐색 힌트를 얻을 수 있을 것 같다.

+) 나는 뭔가 거리를 가능한 크게 하여~ 가장 인접한 거리를 최대로~ 등등 최대로 하라는거냐 최소로 하라는거냐 어캐 풀라는거지 싶으면 parametric search를 떠올린다

 

 

parametric search를 떠올렸으면 문제를 가능한 __중에서 최대 값을 구하는 문제로 바꾼다.

여기서는 공유기를 설치할 수 있는 거리 중에서 최대 값을 구하는 문제로 바꿨다.

 

범위 (l 과 r 사이)는 최대한 크게 잡는다. 

구하는 값을 이분 탐색의 mid로 둔다. 여기서는 공유기 사이의 거리를 mid로 두었다.

 

parametric search에서 주의할 점은 공유기가 3개 있고, 각 거리마다 설치할 수 있는 공유기의 개수(count)를 셌을 때

3개보다 더 많이 설치할 수 있어도 답이 될 수 있다는 것이다.

그래서 count == C(문제에서 주어진 공유기의 개수)인 경우와 count > C인 경우를 나누지 않고 같이 묶었다.

 

공유기를 설치할 수 있는 거리를 찾았다고 그대로 끝내는 것이 아니라, 더 최적화된 답을 찾을 수 있는 가능성이 남아있으므로거리를 의미하는 mid가 커지는 방향으로, 즉, l을 늘려서 범위를 좁히는 방향으로 탐색을 더 진행한다.

 

 

거리를 mid 이상으로 했을 때 공유기를 최대 몇 개 설치할 수 있는지 구하는 부분이 고민이었는데,

1 2 4 8 9 가 있을 때 꼭 공유기를 1에 설치해야하는지에 대한 확신이 없어서 이중 for문으로 시작점을 옮겨가며 count 했더니 시간초과가 났다.

생각해보니 어차피 1에 공유기를 설치하는 게 1을 건너뛰고 2에 공유기를 설치하는 경우를 포함하므로 1부터 시작하는게 맞았다. for문을 하나로 바꾸고 통과했다.