[이분탐색] 백준 #2512 예산 - Python

🗂️ 문제

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

 

💡 접근법

총 예산이 예정 예산을 초과할 경우 예산의 상한액을 설정해야 하며, 이때 이분탐색을 사용한다.

하지만 만약 모든 예산이 배정될 수 있는 경우에는 상한액을 설정할 필요가 없으니 예산의 최댓값을 리턴한다.

 

이분탐색을 위해 low=1, high는 예산들 중 최댓값으로 설정한다.

 

이때 mid를 통해 상한액을 정하고,

상한액보다 적은 예산은 그대로 예산을 적용하되, 상한액을 초과하는 예산은 상한액으로 금액을 산정하여 예산의 합을 계산한다.

 

만약 예산의 합이 총 예산보다 크다면, 상한액을 더 내려야 하므로 high 값을 mid-1로 조정한다.
만약 예산의 합이 총 예산보다 작다면, 이는 상한액을 더 올려야 하므로 low 값을 mid+1로 조정한다.

 

또한, 최대로 예산을 사용해야 하므로, 가능한 상한액 중 최댓값을 구해야 한다.

따라서 이분탐색을 끝까지 수행하여 상한액의 범위를 좁혀나가고, 마지막에 high 값을 리턴한다.

 

😎 내 코드

import sys

N = int(sys.stdin.readline())
budgets = list(map(int, sys.stdin.readline().split()))
total_budget = int(sys.stdin.readline())

if sum(budgets) <= total_budget:
    print(max(budgets))
else:
    low, high = 1, max(budgets)

    while (low <= high):
        mid = (low + high) // 2
        
        new_budgets = []
        for budget in budgets:
            if budget <= mid:
                new_budgets.append(budget)
            else:
                new_budgets.append(mid)

        if sum(new_budgets) > total_budget:  # 예산 초과
            high = mid - 1
        else:  # 예산 가능
            low = mid + 1

    print(high)

 

✅ 정답 확인