[백준] 2110 공유기

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

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

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

 

접근 방법

문제를 해결하지 못해 다른 분이 작성한 해결 방법을 참고하였다.

 

문제에서 요구하는 바는 가장 인접한 두 공유기 사이의 거리를 최대로 하는 것이다. 

 

이는 바꿔 말하면 공유기 사이의 거리를 최대한 공평하게 한다는 것이다.

 

공유기 사이의 거리를 최대한 공평하게 하기 위한 방법으로 먼저 기준이 될 거리인 D(1, 2 , 3, ...)를 정한다. 그리고 각 공유기 사이의 거리를 구해 D 이상일 경우 카운트를 하나씩 늘려간다.

 

카운트가 주어진 C와 동일할 경우 D가 가장 공평한 거리가 되는 것이다.

 

하지만 D를 하나씩 늘려가기에는 주어진 거리의 최대 값이 1,000,000,000 이기 때문에 시간이 매우 오래걸린다. 따라서 시간 복잡도가 O(logN)인 이분탐색을 사용한다.

 

소스 코드

import sys
readline = sys.stdin.readline

def main():
    N, C = map(int, readline().split())
    x = [int(readline()) for _ in range(N)]
    x.sort()

    result = binary_search(N, C, x)
    print(result)

def binary_search(N, C, x):
    left = 1
    right = x[-1] - x[0]
    ans = 0

    while left <= right:
        mid = (left + right) // 2
        cnt = 1

        current = x[0]
        for i in range(1, N):
            dist = x[i] - current
            if dist >= mid:
                cnt += 1
                current = x[i]
        
        if cnt < C:
            right = mid - 1
        else:
            left = mid + 1
            ans = mid
    
    return ans


if __name__ == "__main__":
    main()