공유기 설치

N, C = map(int, input().split())
arr = sorted(list(int(input()) for _ in range(N)))

# 범위: 공유기 거리
left, right = 1, arr[-1]-arr[0]
answer = 0

while left <= right:
    mid = (left + right) // 2       # 공유기 거리의 중간 값
    cnt = 1                         # 0번 위치에 공유기 설치
    prev = arr[0]

    # 최소 mid 간격으로 공유기 최대 설치
    for i in range(1, N):
        if arr[i]-prev >= mid:      # mid보다 먼 거리의 경우 설치
            cnt += 1
            prev = arr[i]           # 공유기 설치 위치 저장

    if cnt >= C:
        answer = mid
        left = mid + 1
    else: right = mid - 1

print(answer)

구하는 값을 이분 탐색의 범위로 설정: 공유기 설치 거리

이전 설치 공유기 위치와의 간격 체크하며 공유기 설치 -> 공유기 개수 체크

mid 간격으로 설치할 경우, 더 많은 공유기 설치 가능 -> 간격 증가(left+1)
mid 간격으로 설치할 경우, 모든 공유기 설치 가능 -> 올바른 간격 저장, 종료 조건(left+1)
mid 간격으로 설치할 경우, 모든 공유기 설치 불가 -> 간격 감소(right-1)