[백준/2110] 공유기 설치

출처: 2110번: 공유기 설치 (acmicpc.net)

2110번: 공유기 설치

 

 아이디어를 떠올리기 쉽지 않은 이진탐색 문제이다. 공유기 간 최소거리를 정해놓고 몇 개의 공유기가 설치될 수 있는지 확인한다. 설치할 수 있는 공유기의 개수를 기준삼아 설치해야 하는 공유기의 개수보다 적으면 최소거리를 적게 잡는다. 반대의 경우엔 이미 설치해야 하는 만큼 설치가 가능하다는 의미이므로 정답을 저장하되, 최대거리를 구하는 문제이므로 더 큰 거리를 두고서도 필요한 만큼 설치할 수 있는지 확인한다. 구체적인 코드는 다음과 같다.

 

n, c = list(map(int, input().split()))
array = []
for _ in range(n):
    array.append(int(input()))
array.sort()

start = 1
end = array[n - 1] - array[0]
answer = 0
while start <= end:
    mid = (start + end) // 2

    pivot = 0
    cnt = 1
    for i in range(1, n) :
        if array[i] >= array[pivot] + mid:
            cnt += 1
            pivot = i
    if cnt < c:
        end = mid - 1
    else:
        start = mid + 1
        answer = mid
        
print(answer)

 이진탐색은 기본적으로 정렬된 리스트에 대해서만 수행할 수 있다는 것을 꼭 잊지 말자. start는 공유기 사이에 발생할 수 있는 최소거리, end는 최대거리이다.

 핵심은 이 부분이다.

for i in range(1, n) :
    if array[i] >= array[pivot] + mid:
    	cnt += 1
        pivot = i

 처음의 기준점(pivot)은 0이다. 1부터 n까지 리스트를 순회하면서 기준점에 거리(mid)를 더한 값보다 큰 좌표에 위치한 집을 발견한 경우 공유기를 설치한다. cnt 변수가 설치된 공유기의 개수를 관리한다. 또한 기준점을 해당 시점에 공유기가 설치된 집의 좌표로 변경한다.

 설치해야하는 공유기의 개수를 c라고 할때 총 설치한 공유기의 개수가 c보다 작다면 거리를 더 좁혀서 탐색해본다. 거리를 좁히면 설치 가능한 공유기의 수도 늘어날 것이다. 반대의 경우에는 c개를 설치 가능하다는 보장이 있으므로, 정답을 저장하고 최대값을 구하기 위해 더 큰 범위에서도 탐색해본다.

if cnt < c:
    end = mid - 1
else:
    start = mid + 1
    answer = mid