[백준/Python] 2512 예산

문제 링크

2512번: 예산

 

문제 풀이

• 예산 요청 금액이 예산보다 작거나 같으면(i <= mid) 예산 요청 금액 만큼의 예산을 받을 수 있고, 예산보다 크면(i > mid) 예산 만큼의 예산을 받을 수 있는데, 이는 for문을 이용해서 작성할 수 있다.
• 이에 따른 총 예산의 합이 M보다 크면(total > m) 예산을 초과하게 되므로 배정할 수 있는 예산의 크기를 줄여야 한다. 반대로 M보다 작거나 같으면(total <= m) 다시 예산의 크기를 늘려야 한다.
• 또한, 배정할 수 있는 예산은 각 예산 요청의 최댓값보다 클 수 없으므로 초기 end 값은 입력 받은 리스트의 최댓값이 된다.

 

전체 코드

import sys

n = int(sys.stdin.readline())
l = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())

start = 0
end = max(l)

res = 0
while start <= end:
    total = 0
    mid = (start + end) // 2
    # mid가 예산일 때의 총 예산 계산
    for i in l:
        if i <= mid:
            total += i
        else:
            total += mid
    # 총 예산은 M보다 클 수 없으므로 예산 재계산
    if total > m:
        end = mid - 1
    else:
        # 현재의 예산과 비교하여 더 큰 값 저장
        res = max(res, mid)
        start = mid + 1

print(res)