[BOJ] 2110 - 공유기 설치

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

2110번: 공유기 설치

import sys
n, c = map(int, sys.stdin.readline().rstrip().split())
data = []
for i in range(n):
    data.append(int(sys.stdin.readline()))

data.sort()
start = 1
end = data[-1] - data[0]

while start <= end:
    count = 1
    mid = (start + end) // 2
    value = data[0]
    for i in range(1, n):
        if data[i] >= value + mid:
            value = data[i]
            count += 1

    if count >= c:
        result = mid
        start = mid + 1

    else:
        end = mid - 1

print(result)

이 문제는 이진 탐색을 이용한 파라메트릭 서치 유형의 문제이다.

집의 개수 N은 20만, 집의 좌표 x의 범위가 10억이므로, 이진 탐색을 이용하여 O(N * log X)의 시간 복잡도로 문제를 해결할 수 있다.

 

풀이 방법은 이진 탐색으로 가장 인접한 두 공유기 사이의 거리를 조절해가며, 매 순간 실제로 공유기를 설치하여 c보다 더 많은 개수의 공유기를 설치할 수 있는지 체크해나가는 것이다. 

while start <= end:
    count = 1
    mid = (start + end) // 2
    value = data[0]
    for i in range(1, n):
        if data[i] >= value + mid:
            value = data[i]
            count += 1

여기서 어려우면서 중요한 점은 공유기를 설치하는 방법을 떠올리는 것이었다. 정답 코드에서는 공유기를 '앞에서부터 차례대로 설치하는 경우'로 다음 집과의 거리가 mid 이상이면 count를 1 증가시키고 value를 다음 집으로 갱신하는 방법을 사용하였다. 공유기 설치가 완료되면 c와 비교하여 c보다 더 크다면 간격을 더 늘려도 되는지 확인하기 위해서 start = mid + 1로 갱신하고 mid를 최적의 결과로 저장해놓는다. start가 end보다 더 커진다면 result를 출력하여 최대 거리를 구한다.