• 문제 링크: https://www.acmicpc.net/problem/2110

설명

이 문제는 어떤 풀이를 써야할지 잡히지 않아 어려움이 있었다.
일단 가장 인접한 두 공유기 사이의 거리를 최대로 라는 말이 이해가 가지 않았다. 이 말은 즉, 공유기 사이의 거리가 최대한 떨어져있도록 설계하라는 말이다.

이분탐색으로 풀려면 어떻게 해야할까?
가장 인접한 두 공유기 사이의 거리를 이분 탐색으로 구하여, 해당 거리에서 설치해야하는 공유기 개수를 만족하는지 확인하는 것이다.

예시를 살펴보자.
예시는 공유기 사이의 거리가 차례로(정렬된 상태에서) 1, 2, 4, 8, 9이다. 이때 최소한의 거리는 1이고 최대는 8이므로 거리의 중앙값은 (1 + 8) // 2로 4가 mid가 된다.

그럼 이 값을 기준으로 현재 집에서 다음 집의 거리가 mid보다 크거나 같다면 공유기를 설치할 수 있다.

먼저 1 다음의 2, 4는 거리가 각각 1과 3만큼 떨어져 있기 때문에 공유기를 설치할 수 없다. 8은 거리가 7, 즉 4 이상이므로 공유기를 설치할 수 있고 9는 8까지의 거리가 1이기 때문에 설치할 수 없다.

이 경우 설치할 수 있는 공유기 수는 2개이므로 적합하지 않다.

그럼 공유기를 더 많이 설치하려면 공유기 사이의 거리를 좁혀서 탐색해야 한다.

이 문제에서 최소한의 거리에서 설치할 수 있는 공유기 개수를 만족하는가 라는 방향으로 문제를 보고 풀었다면 이해에 오랜 시간이 걸리지 않았을 것 같다.

코드

import math, sys

N, C = map(int, s.readline().split())

house = []
for i in range(N):
	house.append(int(s.readline()))
    
house.sort()

start = 1
end = house[-1] - house[0]

answer = 0

if c == 2:
	print(house[-1] - house[0])
else:
	while start <= end:
    	# 공유기 사이의 거리: 몇 개의 공유기가 설치될 수 있는가
    	middle = (start + end) // 2		
        current = house[0]
        count = 1
        
        for i in range(1, len(house)):
        	# 떨어져 있는 거리가 설정값(middle)보다 크거나 같을 때
        	if house[i] - current >= middle:
            	count += 1
                current = house[i]
		
        # 공유기 숫자를 줄인다. -> 간격을 더 늘린다.
        if count >= C:
        	start = middle + 1
            answer = middle
            
		# 공유기 숫자를 늘린다. -> 간격을 줄인다.
        else:
        	end = middle - 1
	
    print(answer)

이 문제를 풀면서 이분탐색에 대한 생각은 명확한 값을 찾기보다는 그 값으로 가까이 가기 위한 작업을 진행한다고 생각했다.