[Python] 예산 - 백준 (이진탐색)

해당 글은 백준 2512번 '예산' 문제를 다룬다.

문제

https://www.acmicpc.net/problem/2512

2512번: 예산

 

설명

해당 문제는 이진탐색으로 해결할 수 있는 문제이다.

주의할 점은 total을 구할 때, mid와 arr[i] 중 최소값으로 구해야하는 점이다.

또한, total이 m보다 크다면, 예산을 초과한 것이므로 end를 mid-1로 줄여서 이진탐색을 다시 해야한다.

 

코드

n = int(input())
arr = list(map(int, input().split()))
m = int(input())

start, end = 0, max(arr)
result = 0
while start <= end:
    mid = (start+end)//2
    total = 0
    for i in range(n):
        total += min(mid, arr[i])

    if total > m:
        end = mid - 1
    else:
        result = mid
        start = mid + 1
print(result)