[Boj] 예산 2512(python)

문제링크 : https://www.acmicpc.net/problem/2512

이진탐색 연습문제이며, 나무자르기와 랜선자르기의 연장선이다.

자세한 설명은 나무자르기와 랜선자르기에 정리되어 있음

import sys
from bisect import bisect_left

N = int(sys.stdin.readline())
moneys = list(map(int, sys.stdin.readline().split()))
K = int(sys.stdin.readline())

moneys.sort()
start = 1
end = max(moneys)

while start <= end:
    result = 0
    if start > end:
        break
    mid = (start + end) // 2
    idx = bisect_left(moneys, mid)
    result += sum(moneys[:idx])

    for money in moneys[idx:]:
        result += mid

    if result > K:
        end = mid - 1
    else:
        answer = mid
        start = mid + 1

print(answer)