[boj 2110 python]공유기 설치

n = 5
c = 3
arr = [1, 2, 8, 4, 9]
# n, c = map(int, input().strip().split())
# arr = [int(input()) for _ in range(n)]

arr.sort()

# mid보다 크거다 같은 간격으로 공유기를 몇개 설치할 수 있는지 return
def router_cnt(mid):
    prev = arr[0]
    cnt = 1  # 설치할 공유기 수를 담는 변수. 기본적으로 baseCase에 먼저 설치하므로 1에서 시작한다
    for i in range(1, n):
        if arr[i] - prev >= mid:  # arr[i] 의 간격이 더 넓으면 설치 가능
            cnt += 1
            prev = arr[i]
    return cnt


# 가장 인접한 공유기 사이 최대 거리를 return하는 함수
def binary_search(c):
    start = 1
    end = arr[-1] - arr[0]  # 최대 간격은 가장 큰 좌표에서 가장 작은 좌표를 뺀 것
    while start <= end:
        mid = (start + end) // 2  # mid가 간격이 된다
        router = router_cnt(mid)
        if router < c:  # 이 간격에서 설치되는 공유기의 수가 c보다 작다면
            end = mid - 1  # 간격을 좁혀야 한다
        elif router >= c:  # 크거나 같다면
            ans = mid  # 정답 후보이므로 ans에 값을 저장해두고
            start = mid + 1  # 간격을 넓혀야 한다.
    return ans


print(binary_search(c))