[Python] 백준 - 2512번 예산(Binary Search)

◈ 오류 정정 및 피드백 환영

2512번: 예산

---

🔎문제 분석

랜선 자르기와 유사한 문제로 이분탐색(Binary Search)으로 접근하면 된다.

[Python] 백준 - 1654번 랜선 자르기(Binary Search)

예산이 모자랄 경우 상한액이 너무 낮은 것이므로 탐색 범위를 넓히면 되고, 예산을 초과하면 상한액을 줄여야하므로 탐색 범위를 좁히면 된다. 랜선 자르기와 마찬가지로 예산이 정확하게 맞아 떨어지더라도 최대 예산을 구해야 하므로 탐색 범위를 넓혀야 한다.

---

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
m = int(input())

l = 0
r = max(a)
while l<=r:
    mid = (l+r)//2
    budget = list(map(lambda x: mid if x>mid else x, a))
    amt = sum(budget)
    if amt <= m:
        l = mid+1
    else:
        r = mid-1
print(r)