[ BOJ ] 백준 2512 - 예산(파이썬 문제 풀이)

문제 링크

2512번: 예산

 

이분 탐색으로 풀 수 있는 예산 문제 입니다.

가능한 예산 중 최대값을 찾기위해 시작 값, 끝 값을 나누어 중간 값으로 범위를 확장, 축소하여 문제를 풀이했습니다.

 

문제 풀이(파이썬)

---

N = int(input())
req = list(map(int, input().split()))
M = int(input())

lt = 1
rt = max(req)
res = 0
while lt <= rt:
    mid = (lt+rt)//2

    res_tmp = 0
    for r in req:
        if r > mid:
            res_tmp += mid
        else:
            res_tmp += r

    if res_tmp > M:
        rt = mid-1
    else:
        res = mid
        lt = mid+1

print(res)