[백준] 공유기 설치.py

import sys
n, c = map(int, sys.stdin.readline().split())
arr = []
for _ in range(n):
    arr.append(int(sys.stdin.readline()))

arr.sort()
start, end = 1, arr[-1] - arr[0]
result = 0
while start <= end:
    mid = (start + end) // 2
    idx, count = 0, 1
    for i in range(1, len(arr)):
        # idx 위치에 공유기 설치했을 때 mid 거리 안에 i 위치의 집까지 전파가 닿지 않을 경우
        if arr[idx] + mid <= arr[i]:
            # 공유기를 하나 추가한다.
            count += 1
            # 다음 집의 위치에 공유기를 설치한다.
            idx = i
    # 공유기 개수가 c보다 작을 경우
    if count < c:
        end = mid - 1
    # 공유기 개수가 c보다 클 경우
    elif count >= c:
        result = mid
        start = mid + 1
print(result)