5일차 (2.21)

백준 2512 예산

설명

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다.

여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.

입력

첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다.

다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다.

이 값들은 모두 1 이상 100,000 이하이다.

그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다.

출력

첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력한다.

예제 입력 1

4
120 110 140 150
485

예제 출력 1

127

예제 입력 2

5
70 80 30 40 100
450

예제 출력 2

100

Pseudo Code

1. 지방의 수를 의미하는 정수 N을 받는다
2. 각 지방의 예산요청을 표현하는 N개의 정수를 리스트로 받기
3. 총예산 M 받기
4. 총예산의 최소 : 0 ~ 최대 : 2번에서 받은 정수중 제일 큰수 의 예산 사이의 중간값 구하기
5. 4번의 결과값(중간값)을 2번의 값에 맞춰서 지급
6. 만약 5번의 결과가 3번 보다 작거나 같다면 최소 값을 중간값+1로 재지정 및 결과값 저장
7. 만약 5번의 결과가 3번보다 크다면 최대 값을 조정
8. 5,6,7 을 반복하며 최소값이 최대값과 동일 하거나 커진다면 종료
9. 각 지자체에 주는 금액은 6번에서 저장한 결과값과 2번의 리스트 의 최소값을 구한다
10. 9번중 최대값을 리턴한다.

Code

N = int(input())
req = list(map(int, input().split()))
total_budget = int(input)

def need_budget(upper_budget : int):
    need_budget = 0
    for i in req:
        need_budget += min(i, upper_budget)
    
    return need_budget

low = 0
high = max(req)
good_budget = -1
res = -1
while low <= high:
    mid = (low + high) //2
    
    if need_budget(mid) <= total_budget:
        low = mid + 1
        good_budget = mid
    else:
        high = mid - 1
for i in req:
    given = min(i, good_budget)
    res   = max(res, given)
print(res)