백준 예산 문제 풀이이다.
국가 예산(m)과 각 지방의 예산 요청이 주어질 때, 실제 배정된 예산들 중 최댓값(정수)을 출력하는 문제이다.
예산 배정은 아래와 같은 2가지 경우가 존재한다.
[1] 모든 요청이 배정될 수 있는 경우
국가 예산으로 각 지방에서 요청한 모든 예산을 지급할 수 있는 경우이므로, 각 지방의 요청 예산 중 최댓값을 출력하면 된다.
[2] 모든 요청이 배정될 수 없는 경우
각 지방에서 요청한 모든 예산의 총 합이 국가 예산보다 큰 경우이다.
따라서 문제의 조건처럼 특정 정수 상한액을 정해서 이 금액보다 많은 예산을 요청한 지방에는 상한액만큼만 지원해야 한다.
두 번째 경우에서 상한액은 어떻게 구할 수 있을까?
여러 방법이 있을 수 있지만, 상한액의 범위가 1 이상 MAX(각 지방의 요청 예산) 이하이고 이 범위에서 정수 단위로 값을 찾아야 하므로 이진 탐색(binary search)로 접근할 수 있다.
참고로 상한액의 최솟값을 1로 둔 이유는 지방의 수 N에 대해 M의 범위가 N 이상이므로, 어떤 경우더라도 각 지방에 1만큼의 예산은 배정 가능하기 때문이다.
이진 탐색 과정에서는 반복문을 통해 각 지방의 요청 예산을 확인하며, 만약 어떤 지방에서 요청한 금액이 현재 예측한 상한액(mid)보다 작다면 예산 요청 합계에 상한액 대신 그 지방의 요청 금액을 더해야 한다.
왜냐면 상한액은 모든 지방의 요청 예산이 국가 예산을 뛰어넘는 경우, 상한액보다 큰 금액을 요청한 지방에만 적용하기 위해 정한 값이기 때문이다.
이렇게 구한 예산 요청 합계가 국가 예산보다 작거나 같다면 현재 mid 값은 상한액 후보가 될 수 있으므로 upper_limit이라고 정의한 상한액의 값을 mid로 업데이트해준다.
코드(정답)는 다음과 같다.
import sys
# 입력
n = int(sys.stdin.readline())
budgets = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
# 각 지방의 예산 요청 합계가 총 예산보다 작거나 같은 경우
if sum(budgets) <= m:
print(max(budgets))
# 각 지방의 예산 요청 합계가 총 예산보다 큰 경우(상한액 배정 필요!)
else:
low, high = 1, max(budgets)
upper_limit = 0
while low <= high:
mid = (low + high) // 2
sum_budgets = 0
for budget in budgets:
sum_budgets += min(budget, mid)
if sum_budgets <= m:
low = mid + 1
# 상한액이 mid일 때, 총 예산으로 모든 지방에 지원 가능!
upper_limit = mid
else:
high = mid - 1
print(upper_limit)