[python] 백준 알고리즘 2110번 공유기 설치, 이진 탐색 풀이

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

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

sta = X[1] - X[0]
end = X[-1] - X[0]

result = 0

while sta <= end:
    mid = (sta + end) // 2  # Gap을 의미함
    val = X[0]
    cnt = 1

    for i in range(1, len(X)):
        if X[i] >= val + mid:
            val = X[i]
            cnt += 1
    if cnt >= C:
        sta = mid + 1
        result = mid
    else:
        end = mid - 1
print(result)

입력 예시

5 3
1
2
8
4
9

출력 예시

3