이진탐색

이것이 코딩테스트다 - 369p 29번 문제

 

 

집의 개수 N

공유기의 개수 C

 

한 집에는 공유기 1개 설치할 수 있음

공유기와 공유기의 사이를 멀게 설치해야 함

(가능한 거리를 크게!)

 

 

n, c = list(map(int, input().split('')))  #집의 개수 n, 공유기 개수 c 입력받기

array=[]  #전체 집의 좌표 정보 입력받기 
for _ in range(n):
	array.append(int(input()))
array.sort() #이진 탐색을 위해 정렬

start=1  //최소 거리
end=array[-1] - array[0]  #최대 거리
result=0

while(start <= end):
	mid = (start + end) //2 #가장 가까이에 있는 두 공유기 사이의 거리
	value =array[0]
	count=1
	
	for i in range(1,n): #앞에서부터 설치
		if array[i] >=value + mid:
			value=array[i]
			count+=1
	if count >= c: # c개 이상의 공유기를 설치할 수 있는 경우, 거리 증가
		start=mid+1
		result = mid  #최적의 공유기 설치 장소 저장
	else:  #c개 이상의 공유기를 설치할 수 없는 경우, 거리 감소
		end=mid-1

print(result)