백준 2110 [python]

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

import sys

def binary_search(start, end):
    global res
    if start > end:
        return
    mid = (start + end) // 2
    
    cnt = 0
    temp = 0
    for i in range(1, n):
        temp += x[i] - x[i - 1]
        if temp >= mid:
            cnt += 1
            temp = 0
    
    if cnt < c - 1:
        binary_search(start, mid - 1)
    else:
        res = mid
        binary_search(mid + 1, end)
    
n, c = map(int, input().split())
x = []
for i in range(n):
    x.append(int(sys.stdin.readline()))
x.sort()

res = 0
start = 1
end = (x[-1] - x[0]) // (c - 1)

binary_search(1, end)
print(res)

풀이 방법이 바로 생각이 나지 않았다. 처음에는 집 좌표 리스트를 어떻게 이분 탐색해보려고 했다. 앞으로 이런 문제를 만났을 때 알고리즘을 어떤 부분에 왜 적용시켜야 하는지 계속 생각하면서 똑똑하게 풀 수 있게 노력해야겠다.

공유기는 최선을 다해 널찍히 떨어뜨러야 하고, 그 상태에서 가장 짧은 거리를 구해야 한다. 사고과정의 핵심은 한 길이를 가장 넓게 퍼뜨린 공유기들 중 가장 작은 거리라고 가정하고 검사하는 것이라고 생각한다.