[백준/이진탐색] 2512번 예산

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

문제

여러 지방 N개의 예산 요청을 받고, 국가 예산의 총액 이하로 예상을 배정합니다.

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정합니다.
   ex. [10, 10, 10, 20] 의 예산을 요청 받았고, 총 금액이 50이라면 국가 예산 총액에서 요청한 금액들을 모두 배정할 수 있습니다.
   즉, [10, 10, 10, 20] 예산 그대로 배정됩니다.
2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상의 예산 요청에는 모두 상한액을 배정합니다. 상한액 이하의 예산 요청에 대해서는 요청한 금액을 그대로 배정합니다.
   ex. [110, 120, 140, 150]의 예산을 요청 받았고, 총 금액이 485인 경우에
   상한액을 127로 잡으면 [110, 120, 127, 127]의 예산이 배정됩니다.

출력

배정된 예산들 중 최댓값인 정수를 출력합니다.

 

풀이

from sys import stdin

input = stdin.readline

N = int(input())
# 요청한 예산
prices = list(map(int, input().split()))
# 국가 예산의 총액
total = int(input())

# 국가 예산의 총액으로 배정가능할 경우 최댓값을 출력합니다.
if sum(prices) <= total:
    print(max(prices))
else:
    start, end = 0, max(prices)

    while start <= end:
    	# 중앙값을 가져옵니다.
        mid = (start + end) // 2
        
        # 현재의 중앙값을 상한액으로 보았을 때, 총합을 계산합니다.
        result = 0
        for i in prices:
            if i > mid:
            	# 상한액 이상의 예산요청에는 모두 상한액을 배정한다.
                result += mid
            else:
            	# 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.
                result += i
                
        # 국가 예산 이하인 경우
        if result <= total:
            start = mid + 1
        # 국가 예산에 초과인 경우, 상한액을 내립니다.
        else:
            end = mid - 1
    print(end)