BOJ - 공유기 설치(2110)

실버2 : 파라메트릭 서치 문제이다.

생각

파라메트릭 서치 문제이다. 일단 완전 탐색이 불가하고, 답을 제시했을 때 분기를 만들 수 있다는 점에서 바로 접근했다.

1. 인접한 집간의 최대 거리를 제시한다.
2. 제시한 거리를 보다 크거나 같은 곳에 공유기를 설치했을 때 몇개를 설치할 수 있는지를 반환한다.
3. 그 반환한 값(즉 내가 제시한 거리로 공유기를 설치했을 때 대수)이 C와 어떤지 비교한다.
4. C보다 작다면 거리를 너무 크게 잡았으므로 거리를 줄여서 제시한다.
5. C보다 같거나 크다면 이 값은 후보가 될 수 있는 값이다. 후보인 이유는 지금 제시한 거리보다 큰 값에서 C와 같은 값이 나올 수 있기 때문에 더 탐색한다.

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<queue>
#include<functional>
using namespace std;
typedef long long ll;
int N, C;
int a[200000];
 
int f(int num){
    int count = 1;
    int before = 0;
    for (int i = 1; i < N; i++) {
        if (a[i]-a[before] >= num) {
            count++;
            before = i;
        }
    }
    return count;
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> N >> C;
    for (int i = 0; i < N; i++) cin >> a[i];
    sort(a, a+N);
 
    int start = 1, end = 1e9, ans = 0;
 
    while (start <= end) {
        int mid = (start+end)/2;
        int count = f(mid);
 
        if (count < C) {
            end = mid - 1;
        } else {
            ans = max(ans, mid);
            start = mid + 1;
        }
    }
    cout << ans << '\n';
    return 0;
}

Reference

• 백준(2110번) - 공유기 설치