답지 결국 봄 ㅠㅠ 예전에 풀었던 문제였는데도. 겸손 겸손

어려웠던 점

1. 이분 탐색이란걸 알았지만, 이분 탐색 문제가 항상 그렇듯 어떠한 걸 이분 탐색 해야되는지 감이 안잡혔다. 결국 답을 보니, 가능한 max_possible_dist를 나누면서 이분탐색 하는 거였다....
2. max_possible_dist = (start + end) // C로 했다가 시간초과 뜸 그냥 나누기 2 해야됨
3. start = max_possible_dist + 1 & end = max_possible_dist -1 를 안했던 이유는 집 길이만 문제에서 10억으로 해놨는데 +- 1씩 하면 시간 초과 뜰거라 생각함. 근데 걍 max_possible_dist도 같이 넣어서 업데이트해주기 때문에 후딱 됨

# 답지 세번 참조
import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

N, C = map(int, input().split())
ward = [int(input()) for _ in range(N)]
ward.sort()

start = 1
end = ward[-1] - ward[0]
max_dist = 0

while start <= end:
    # 끝집과 끝집 사이 거리가 10이고 공유기 4개 필요하면, 최대 가능 길이가 10//4 = 2 임
		# 이 주석은 틀린주석임. 무한루프 만듬 
    max_possible_dist = (start + end) // 2
    # 맨 앞집은 와드
    cnt = 1
    current_pos = 0

    # 한집씩 돌면서 설치가능하면 와드박기
    for i in range(1, N):
        if (ward[i] - ward[current_pos] >= max_possible_dist):
            cnt +=1
            current_pos = i

    # 더 많이 설치 됬다는 얘기니까 거리가 좀 더 길어져도 됨
    if cnt >= C:
        max_dist = max(max_dist, max_possible_dist)
        start = max_possible_dist + 1

    # 덜 설치 됬으니까 거리가 짧아져야됨
    else:
        end = max_possible_dist -1

print(max_dist)