소스코드

import sys
input = sys.stdin.readline

N,C = map(int, input().strip().strip())
X = sorted([int(input()) for _ in range(N)])
result = 0 # 결과 : 가장 인접한 두 공유기 사이의 최대 거리

start, end = 1, (X[-1] - X[0])
while start <= end:
	mid = (start + end) // 2
	mid_value = X[mid] # 공유기 간 최소 거리 후보
	
	# 거리를 늘려나가기
	last_installed = X[0]
	count = 1 # 현재 거리로 설치된 공유기 개수 : 첫번째 집에 공유기 설치
	for i in range(1,N):
		if (X[i] - last_installed) >= mid_value:
			last_installed = X[i]
			count += 1
		
	# 카운트된게 목표했던 것보다 크다 -> 더 늘려봐도 된다
	if count >= C:
		start = mid + 1
		result = mid # 조건을 만족할 때 갱신
	else:
		end = mid - 1

print(result)	

풀이

• 우선 저는 보통 10^9(10억) 숫자 범위가 등장하면 이분탐색을 곧바로 떠올리는 편입니다.
• 이 문제는 보통의 이분탐색 목적과는 약간 다릅니다. 이번 문제의 이분탐색 대상은 공유기 간 최소 거리입니다. 즉 전체 배열의 양 끝 인덱스를 이용해서 절반씩 줄여나가며 값을 찾아나가는 형태가 아니라, 거리를 이용해 절반씩 해치워나간다고 생각하시면 됩니다.
  • 최소거리(1)과 최대거리(X[-1] - X[0])으로 start,end를 초기화합니다
  • mid값은 이 최소/최대거리의 중간값입니다.
  • 이 mid값이 현재 탐색의 인접 공유기의 최대거리라고 생각하고 각 공유기를 순회하며 mid값 이상의 거리를 가지면 카운트를 갱신합니다.
  • 순회가 끝나고 카운트값이 C(목표)보다 크거나 같다는 것은 **mid값(인접 공유기의 최대거리 후보)**을 증가시켜봐도 된다는 뜻입니다. 현재의 최대거리보다 늘려서 공유기를 설치해야 다음 탐색에서는 카운트값이 작아지겠죠. 이때 같다(등호) 표현이 붙는 이유는, 최대한 mid값(인접 공유기의 최대거리 후보)을 키워봐야하기 때문입니다.
    • 만약 그게 아니면 오히려 감소하면 됩니다.
• 마지막으로 결과를 출력하면 끝입니다.