[BOJ] 예산

---

코드

from sys import stdin
input = stdin.readline

# input
N = int(input())
budgets = list(map(int, input().split()))
total_budget = int(input())

if sum(budgets) <= total_budget:
    # 총예산으로 충분하면 예산요청 중 최댓값 출력
    print(max(budgets))
else:
    # 총예산으로 충분하지 않으면 이분탐색으로 최적의 상한액을 탐색
    start, end = 0, total_budget
    while start <= end:
        mid = (start + end) // 2    # 상한액
        # 상한액을 기준으로 예산분배한 결과의 합 구하기
        total = sum(map(lambda x: x if x <= mid else mid, budgets))
        # 합을 총예산과 비교하여 상한액 조정
        if total <= total_budget:
            start = mid + 1
        else: 
            end = mid - 1

    print(end)

결과

풀이 방법

• 총 예산의 범위가 크고 최적의 상한액을 구해야 하므로 이분탐색으로 해결하였다.
• while문 조건을 start <= end 로 지정했으므로 탈출 시점에 start는 end보다 1 크다. 따라서 탈출후에 정답으로 end를 출력하거나 (start-1)을 출력하면 된다.

---