[백준/파이썬] #1477

처음에는 접근을 잘못 했었다. 막연히 제일 큰 값을 2로 나눠 주기만 하면 된다고 생각했어서, 테스트 케이스를 일부 통과하지 못했다. 

import heapq


def solution():
    sorted_arr = sorted(arr)
    sorted_arr.insert(0, 0)
    sorted_arr.append(L)
    heap = []

    for i in range(N+1):
        dist = sorted_arr[i+1] - sorted_arr[i]
        heapq.heappush(heap, -dist)
    
    for _ in range(M):
        dist = (-1) * heapq.heappop(heap)
        left_dist = dist // 2
        right_dist = dist - left_dist
        heapq.heappush(heap, -left_dist)
        heapq.heappush(heap, -right_dist)

    dist = heapq.heappop(heap)
    return (-1) * dist


if __name__ == "__main__":
    N, M, L = map(int, input().split())
    arr = None
    if N == 0:
        arr = []
    else:
        arr = list(map(int, input().split()))
    
    print(solution())

 

알고보니 휴게소가 없는 최대 길이(result)를 이분탐색으로 찾는 문제였다. 문제 힌트로 이분탐색이라는 건 알았는데 어떻게 풀지를 몰랐었는데, 풀이를 보니 이해가 되었다. 

def solution():
    sorted_arr = sorted(arr)
    sorted_arr.insert(0, 0)
    sorted_arr.append(L)
    start, end = 1, L-1
    result = 0
    while start <= end:
        count = 0
        mid = (start + end) // 2
        for i in range(1, len(sorted_arr)):
            if sorted_arr[i] - sorted_arr[i-1] > mid:
                count += (sorted_arr[i]-sorted_arr[i-1]-1) // mid
        if count > M:
            start = mid + 1
        else:
            end = mid - 1
            result = mid
    return result


if __name__ == "__main__":
    N, M, L = map(int, input().split())
    arr = None
    if N == 0:
        arr = []
    else:
        arr = list(map(int, input().split()))
    print(solution())