[백준 2512] 예산(Python)

2021.08.18 수정

• 이분탐색 과정에서 상한액을 높이고 낮추는 기준을 반대로 설명했습니다. 이 부분을 수정했습니다.
• 총 예산 초과시 상한액을 높인다 -> 상한액을 낮춘다.
• 총 예산보다 작거나 같으면 상한액을 낮춘다. -> 상한액을 높인다.
  
  

1. 아이디어

우리가 구해야하는 것은 배정된 예산들 중 최대 값을 구하는 것이다. 문제에서 언급한 것처럼, 총 예산이 한정적이기 때문에 지방의 예산 요청대로 배정할 수 없는 경우가 존재한다. 예산을 만족하면서, 배정된 지방의 예산 중 가장 큰 값은 어떻게 구할까. 바로 총 예산을 만족하면서, 상한액을 최소화하면 된다. 다시 말해, 우리는 이분탐색으로 최소 상한액을 찾으면 된다.

상한액에 대한 제약조건이 없으므로, 가능한 상한액의 범주 중 최소 값은 0으로 설정했다. 따라서 left = 0이다. 반면 가능한 상한액의 범주 중 최대 값은 총 예산으로 설정했다. 따라서 right = 총 예산이다.

이분 탐색으로 획득한 상한액(mid)를 고려하여, 지방 예산을 책정하고 그 합을 구해본다. 만약 그 합이 총 예산이 넘어가면, 상한액을 낮춰야한다.(right = mid - 1) 반대로, 그 합이 총 예산보다 작거나 같으면, 최대 값을 갖는 지방예산을 찾는다. 그리고 상한액을 높인다.(left = mid + 1)

2. 코드

import sys

n = int(sys.stdin.readline().rstrip())
budgets = list(map(int, sys.stdin.readline().rsplit()))
MAX = int(sys.stdin.readline().rstrip())

total = sum(budgets)
if total <= MAX: print(max(budgets))
else:
    left = 0
    right = MAX
    answer = 0
    while left <= right:
        mid = (left + right) // 2
        _max = 0
        total = 0
        exceed = False

        for budget in budgets:
            k = min(budget, mid)
            total += k
            if total <= MAX: _max = max(k, _max)
            
            else:
                exceed = True
                _max = 0
                break

        if not exceed:
            answer = max(answer, _max)
            left = mid + 1
        
        else: right = mid - 1

    print(answer)