#394 백준 파이썬 [2512] 예산 - 이분탐색

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

 

SOLUTION

이분탐색으로 풀 수 있는 문제다.

이분탐색에 대한 정의를 알고 오길 추천한다. (https://claude-u.tistory.com/267)

 

예산 금액을 움직여 균등하게 분배할 수 있는 상한선을 구하는 문제다.

 

1) 가장 적음 금액 0을 start로, 가장 큰 상한선 max(budget)을 end로 둔다.

2) 이분탐색이 끝날 때까지 while 문을 돌린다. 혹은 모든 예산을 배정해도 부족함이 없을 경우(total_budget > M)는 max(budget)을 출력한다.

 

3) mid를 start와 end의 중간으로 두고, mid와 예산(i) 중 작은 값을  total_budget에 더해준다.

4-1) total_budget이 목표 수준(M)을 초과하면 mid-1을 end로 두고 다시 while문 반복

4-2)  total_budget이 목표 수준(M)을 이하면 mid+1을 start으로 두고 다시 while문 반복

5) start와 end가 같아지면: 조건을 만족하는 상한선을 찾으면 탈출한다.

6) 결과값인 mid출력

PYTHON CODE

N = int(input())
budget = list(map(int, input().split()))
M = int(input())

start, end = 0, max(budget)
total_budget = 0

if sum(budget) >= end:
	print(max(budget))
else:
    while start <= end:
        mid = (start+end) // 2

        total_budget = 0
        for i in budget:
            total_budget += min(mid, i)

        if total_budget > M:
            end = mid - 1
        else:
            start = mid + 1
    print(mid)