[BaekJoon] 2110번 : 공유기 설치

2110번 : 공유기 설치

공유기를 c 개 설치하는 경우 가장 인접한 공유기의 거리의 최댓값을 구하면 된다.

가장 먼저 떠오르는 방법은 공유기 c 개를 설치하는 조합을 모두 구해 각자 공유기 사이의 거리의 최솟값을 구한다음 그 중 최댓값을 뽑으면 답을 구할 수 있다.

하지만 집의 개수는 최대 200,000 개 이기 때문에 이 방법으로는 절대 구할 수 없다.

따라서 가장 인접한 공유기 사이의 최대거리를 범위로 정해 이진탐색을 통해 찾아야 한다.

공유기를 3개 설치할 수 있고 [1, 2, 4, 8, 9] 의 위치에 있는 집 5개가 있다.

가장 인접한 공유기 사이의 최대거리는 1 ~ 8 이 될 것이다.

STEP 1

[1, 8] 의 중간 값인 4 를 가지고 공유기를 설치해 본다.

[1, 2, 4, 8, 9] 1, 4 번에만 설치를 할 수 있다.

공유기 사이의 거리를 4로 두었을 때 c 개보다 적게 설치 할 수 있다.

따라서 공유기 사이의 거리를 줄여볼 필요가 있다.

STEP 2

[1, 3] 의 중간 값인 2 를 가지고 공유기를 설치해 본다.

[1, 2, 4, 8, 9] 1, 4, 8 번에 설치를 할 수 있다.

c 개 이상의 공유기를 설치 할 수 있기 때문에 이번엔 공유기 사이의 거리를 늘려볼 필요가 있다.

STEP 3

[3, 3] 의 중간 값인 3 을 가지고 공유기를 설치해 본다.

[1, 2, 4, 8, 9] 1, 4, 8 번에 설치를 할 수 있다.

c 개 이상의 공유기를 설치 할 수 있기 때문에 공유기 사이의 거리를 늘려볼 필요가 있다.

STEP 4

[4, 3] start 의 값이 end 값 보다 커졌기 때문에 가장 인접한 공유기 사이의 최대거리는 STEP 3 에서 구한 3 임을 알 수 있다.

어떤 값을 이진 탐색의 범위로 잡고 풀어야 할지, 그 범위를 어떻게 갱신해 가며 답을 구해야 할지 정하는게 가장 어렵다..

---

def solution():
	answer = 0
	start = field[1] - field[0]
	end = field[-1] - field[0]

	while start <= end:
		mid = (start + end) // 2

		antenna = field[0]
		antenna_cnt = 1
		for i in range(1, n):
			if field[i] >= (antenna + mid):
				antenna = field[i]
				antenna_cnt += 1

		if antenna_cnt >= c:
			start = mid + 1
			answer = mid
		else:
			end = mid - 1

	return answer


if __name__ == '__main__':
	n, c = map(int, input().split())
	field = [int(input()) for _ in range(n)]
	field.sort()

	print(solution())