파이썬)예산

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

2512번: 예산

 

 

n = int(input())

arr = list(map(int, input().split()))
money = int(input())

start = 0
end = max(arr)

max_log = 0

if sum(arr) <= money:
    print(max(arr))

else:
    while start <= end and start <= money:
        mid = (start + end) // 2

        log = 0
        for i in arr:
            if i > mid:
                log += mid
            else:
                log += i
        if log <= money:
            if max_log < log:
                max_log = log
            start = mid + 1
        else:
            end = mid - 1

    print(end)

해당 문제는 이분법으로 간단하게 풀 수가 있다.

start를 0으로,

end를 max(arr)로 정한 다음, 

모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다

라는 조건을 검사한 후 while문을 돌린다.