[백준/BOJ] 2110 공유기 설치 (c++)

[백준/BOJ] 2110 공유기 설치 (c++)

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

2025.02.18 - [Competitive Programming] - 06. 정렬 (Sorting Theory) - Binary Search

06. 정렬 (Sorting Theory) - Binary Search

---

20만개의 집이 주어지고 그 집에 C개의 공유기를 배치해야 합니다.

 

그런 경우 C개를 잘 설치해서 가장 인접한 두 공유기 사이의 최대 거리를 찾아야 합니다.

 

최대한 넓게 설치해야 하기 때문에 왼쪽에서 오른쪽으로 공유기를 배치한다고 가정했을 때 첫번째 집에는 항상 공유기가 설치되는 것이 적절합니다.

 

집의 개수가 20만개 이므로 20만개에 C개를 배치하는 조합을 다 계산해 보는 것은 시간복잡도 상 불가능합니다.

 

그렇다면 다른 식으로 접근을 해야하는데 우선 좌표는 최대 10억까지 주어지므로 정답이 될 후보는 10억보다 작습니다.

 

찾고자 하는 값이 인접한 두 공유기 사이의 최대 거리라면 아래와 같이 생각할 수 있습니다.

 

f(k)를 k 간격으로 이상으로 C개의 공유기를 배치할 수 있으면 true, 그렇지 않다면 false를 리턴하는 함수라고 정의했을 때, 만약 정답이 5 인경우

 

f(4) --> true

f(5) --> true

f(6) --> false

f(10..) --> false

 

위와 같이 나타날 것이므로 파라메트릭 서치를 적용할 수 있습니다.

 

최대 10억개의 정답 후보중에서 k길이 이상으로 설치할 수 있는 가장 큰 값을 Binary Search 로 찾는다면 O(logN)에 문제가 풀리게 됩니다.

 

solve() 에서는 Binary Search로 search() 함수의 결과가 true 인 가장 큰 값을 찾습니다.

search() 에서는 현재 탐색 중인 구간의 길이가 k보다 작다면 구간을 늘려가고

 

현재 탐색 중인 구간의 길이가 k 이상이 된다면 그 위치에 공유기를 배치했다고 가정하고 다시 탐색을 시작합니다.

 

첫번째 집에는 항상 공유기가 설치되어 있을테니 C-1 개 배치가 된다면 k간격 이상으로 배치가 가능한 경우입니다.

---

 

#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, e) for (int i=s; i<e; i++)
#define MAX 1000000000
int N, C, x;
vector<int> a;

int search(int k) {
    int x = a[1]-a[0], left = 0, right = 1, c = 0;
    while (left <= right && right < N) {
        if (x >= k) {
            left = right;
            right = left+1;
            x = a[right]-a[left];
            c++;
            if (c == C-1) {
                break;
            }
            continue;
        }
        right++;
        x += a[right]-a[right-1];
    }
    if (c == C-1) {
        return 1;
    }
    return 0;
}
int solve() {
    int k = 0;
    for(int i=MAX/2; i>=1; i/=2) {
        while (search(i+k)) k += i;
    }
    return k;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> C;
    REP(i, 0, N) {
        cin >> x;
        a.push_back(x);
    }
    sort(a.begin(), a.end());
    cout << solve();
    return 0;
}