[BOJ] 2110번 공유기 설치 ★

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

2110번: 공유기 설치

 

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

min_gap = 1
max_gap = arr[-1]-arr[0]
answer = 0
while min_gap <= max_gap:
    gap = (min_gap+max_gap)//2
    cnt = 1
    val = arr[0]
    
    for i in range(n):
        if arr[i] >= val+gap: 
            cnt += 1
            val = arr[i]
    
    if cnt >= c:    # c개 이상의 공유기를 설치할 수 있다
        min_gap = gap+1
        answer = gap
    else:            # c개 이상의 공유기는 설치할 수 없다
        max_gap = gap-1

print(answer)

이진 탐색으로 풀어야 할 문제라고는 생각했는데, 이진 탐색을 해야하는 주체가 집의 위치가 아니라 gap 변수일줄은 생각도 못했다.

비슷한 문제로 여기가 있다.

 

도출해내야 하는 답의 범위를 이진탐색의 주체로 하여, 계산 과정을 최소화하는 게 핵심이다.