백준) 2110 공유기 설치

공유기 설치

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

N개 집의 위치가 일직선 상에 주어지고, 공유기의 갯수 C가 주어진다.

공유기는 집에만 설치 할 수 있을 때, C개를 적절하게 모두 설치하고자 한다.

이 때 설치 가능한 경우들 가운데, 가장 인접한 공유기 쌍의 거리는 최대 몇 까지 가능할까?

C가 2개라고 생각해본다면, 최인접 공유기 쌍간 거리는 시작집과 끝집 사이의 거리다.

C가 3개일 때 부터 고민을 해봐야 하는데, 모든 설치 가능한 경우를 시뮬레이션할 수 도 있다.

하지만 시간이 부족하므로 어떠한 최적화가 필요하다.

만약 최대거리가 x가 되게 시도해보고 성공한다면, x보다 작은 거리는 시도 해볼 필요가 없다.

따라서 이분탐색을 생각해 볼 수 있고, 집의 좌표는 최소 1, 최대 10억 이므로 log로 따지면 30번 안에 찾을 수 있다.

시도하는 과정은 어떻게 구현해야 할까?

그리디적으로 생각해보면 간략히 구현할 수 있다.

만약 중간 집들을 이용했을 때 현재 시도하는 거리가 유효하다면,

당연히 중간 집들의 맨 처음 집 대신 처음 집에 공유기를 심어도 유효하다는 사실은 변하지 않는다. 

만약 중간 집들 중 처음 집이 가장 인접한 공유기 쌍 중에 하나 였다면, 오히려 최대 길이는 늘어날 가능성이 있다.

아니었다면 최대 길이는 그대로 있다.

유효한 시뮬레이션임은 변하지 않는다.

따라서 우리는 처음 집에 공유기를 설치하고 나머지 과정을 시뮬레이션 하면 된다.

다음 집들을 살펴보면서 현재 시도하고 있는 최대길이를 유효하게만 해준다면 공유기를 심어도 되는 것이다.

코드로 옮기면 다음과 같다.

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n, c;
int home[200000];
 
bool chk(int mid) {
    int cnt = 1;
    int cur = 0;
    int next = 1;
    
    while (next <= n - 1) {
        if (home[next] - home[cur] < mid)
            next++;
        else {
            cnt++;
 
            if (cnt == c)
                return true;
 
            cur = next;
            next = cur + 1;
        }
    }
    
    return false;
}
 
int main() {
    scanf("%d %d", &n, &c);
 
    for (int i = 0; i < n; ++i)
        scanf("%d", &home[i]);
        
    sort(home, home + n);
 
    int left = 1, right = home[n - 1] - home[0];
    int ans = 0;
 
    while (left <= right) {
        int mid = (left + right) / 2;
 
        if (chk(mid)) {
            if (ans < mid)
                ans = mid;
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
 
    printf("%d", ans);
 
    return 0;
}