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