우선 이 문제는 이분탐색을 이용하여 풀어야 한다. 하지만 이분탐색을 하기위해 start 와 end 조건을 어떻게 설정해야 하는지 때문에 애를 먹었던 문제이다.
이 문제에서는 기존 기본문제와 다르게 인덱스값을 start,end로 두는게 아닌 각 공유기간의 최소거리와 최대거리를 start, end로 두어야 한다.
1. 집의 개수와 공유기의 개수를 n,c로 입력받는다.
2. start = 1(설치된 공유기 간 최소거리), end = home[-1] - home[0](설치된 공유기 간 최대거리)를 설정한다.
3. 가장 앞의 집에 공유기를 처음에 설치 후 이분탐색 시작
4. 만약 공유기의 개수가 2개면 최대거리는 첫 집부터 마지막 집이 되므로 바로 출력
5. 이분탐색을 진행해 가면서 cnt(공유기의 개수)가 c보다 커지면 공유기 간의 거리를 더 길게 설정할 수 있으므로 설치거리(mid)를 더 늘려가며 다시 이분탐색
6. c개 보다 갯수가 더 적어지면 거리를 더 좁혀야 하므로 mid를 줄여가며 이분탐색
7. 반복이 종료되면 result(정답) 도출 가능
#정답코드
import math
n,c = map(int,input().split())
home = []
for i in range(n):
home.append(int(input()))
home.sort()
start = 1
end = home[-1] - home[0]
result = end
if c < 3:
print(result)
else:
while start <= end:
mid = (start+end) // 2
point = home[0]
cnt = 1
for i in range(1,len(home)):
if abs(home[i] - point) >= mid:
cnt += 1
point = home[i]
if cnt >= c:
result = mid
start = mid + 1
elif cnt < c:
end = mid - 1
print(result)