[#알고리즘/이진 탐색/[백준]2512번:예산(python)]

Question

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

Solution

1. 시작점을 1, 끝점을 예산 요청 금액이 가장 큰 값으로 설정한다.
2. 중간점을 상한액으로 설정한다.
3. 예산 요청 금액이 상한액보다 크면 상한액을 배정하고, 작으면 요청 금액 그대로 배정한다.
4. 시작점과 끝점이 같아지면 조건을 만족하는 상한액(즉, 배정된 예산의 최댓값)은 결국 (mid-1)한 끝점 값이 된다.

Code

import sys

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

start = 0
end = max(amount)

while(start <= end) :
    total = 0
    mid = (start + end) // 2
    for a in amount :
        if a > mid :
            total += mid
        else :
            total += a
    if total < m :
        start = mid + 1
    else :
        end = mid - 1
        
print(end)