백준, BOJ, 2110번, 공유기 설치 C++ [CPP] ★★

이건 문제가 조금 이해하기 어려웠다.

 

 

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

 

---

 

#맞은 풀이

#include <bits/stdc++.h>

using namespace std;

int N,C;
vector<int> house; //좌표는 0부터 10억 가능.
int answer = -1;


//공유기 사이의 거리를 최소 dist 이상으로 설치할 수 있는지.
bool Check(int dist){

    int cur = house[0];
    int cntRouter = 1;

    for(int i = 1; i<N; i++){
        int temp = house[i] - cur;
        if(temp >= dist){
            cntRouter++;
            cur = house[i];
        }
    }
    
    // 더 사용하면 안된다.
    if(cntRouter >= C)
        return true;
    else
        return false;
}

//해당 범위에서 true인지 체크
int Search(int start, int last){
    
    if(start <= last){
        int mid = (start + last) / 2;
        
        if(Check(mid)){
            answer = max(mid, answer);
            return Search(mid+1, last);
        }else{
            return Search(start, mid-1);
        }
    }
    return start;
    
}



int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    //1. 입력
    cin >> N >> C;
    for(int i = 0; i<N; i++){
        int x;
        cin >> x;
        house.push_back(x);
    }
    //2. 정렬
    sort(house.begin(), house.end());
    
    //3. 어떤 넓이가 최대값을 가질 수 있는지 탐색
    int left = house.front(); //처음 좌표
    int right = house.back(); //마지막 좌표
    
    int M = right - left;
    //최소 집 사이의 거리는 1
    Search(1, M);
    
    cout << answer;
    
    return 0;
}

 

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.라고 했는데

2가지 조건이 있다.

1.가장 인접한 두 공유기 사이의 거리를 최대로 한다

2. 공유기를 C개까지만 설치해야 한다.

 

이게 어떻게 이분탐색을 적용할까? 파라메트릭 서치를 어떻게 적용할까? 가 문제다.

뭐 그냥 숫자를 이분탐색으로 내려가면서 맞추면 되겠지 했지만

해당 거리가 최대가 되게 공유기 설치가 되는지는 어떻게 확인을 해야하나? 가 문제였다.

근데 모든 공유기가 해당 거리를 가지는 것은 아니었다.

 

가장 인접한 공유기 사이의 거리를 최대로 하라는 말이었다.

즉, 가장 인접한 공유기만 바꾸면 되는 것이다.

다시 말하면 다른 공유기 사이의 거리는 그것보다 길어도 된다는 말과 같다.

이것을 이해하지 못하면 풀지 못한다.