❓2512번 : 예산
📈 문제 요약
각 지방의 예산 요청 금액을 정해진 총액 이하에서 가능한 한 최대의 예산으로 배정할 때 배정된 예산들 중 최댓값을 구하면 되는 문제
🤨 접근법
예산을 B원 측정하면 정해진 예산 내로 각 지방에 배정할 수 있는가? 라는 결정 문제를 통해 정해진 예산 내로 각 지방에 배정할 수 있는 최대 B를 구하는 최적화 문제를 해결해야 한다.
일단 특정 B원이 정해진 예산 내로 각 지방에 배정할 수 있는 최대 금액, 답이라면 B원보다 많이 배정할 시 정해진 예산을 초과하게 된다. B를 1원부터 측정해 결정 문제(각 지방에 배정 가능?)에 대입하면서 순차적으로 답을 찾아가는 방법도 있지만 M의 범위가 최대 1,000,000,000이기 때문에 O(N)의 복잡도로도 시간 초과를 벗어나기 힘들 것이다.
그렇기 때문에 이분 탐색을 적용한다. 파라메트릭 서치의 전형적인 접근법이다. 예산을 0원부터 요청 예산의 최대값까지 배정할 수 있을 때 low를 0으로 두고, high를 max(requests)로 두어 중간 값에 해당하는 mid를 배정 예산의 상한으로 두면 결정 문제를 만족(각 지방에 배정 가능?)하는지 검사한다. 만약 만족한다면 가장 먼저 만족하지 않는 B를 찾기 위해 low를 mid+1로 두어 더 높은 예산 범위에서 탐색을 하도록 하고, 만족하지 않는다면 high를 mid-1로 두어 더 낮은 범위에서 탐색을 하도록 한다. 위 과정을 low가 high를 역전할 때까지 반복했을 때 high의 배정 예산 상한 B, 즉, 답이 담겨있다. 이 과정은 이전 문제(달팽이는 올라가고 싶다)에 정리해두었다.
이제 배정 가능한 예산의 최대 상한 B를 찾았으므로 지방의 요청 금액들의 최대값이 이 상한 B를 넘지 않으면 그 최댓값을 출력하고, 요청 금액들의 최대값이 상한 B를 넘지 않으면 B를 출력한다.
🔡 코드
import sys
input = sys.stdin.readline
def is_satisfy(B):
result = 0
for request in requests:
result += request if request <= B else B
return result <= M
def allocate_budget(low, high):
while low <= high:
mid = (low+high) // 2
if is_satisfy(mid):
low = mid+1
else:
high = mid-1
return high
N = int(input()) # 3 <= N <= 10,000
requests = list(map(int, input().rstrip().split())) # 1 <= request <= 100,000
M = int(input()) # N <= M <= 1,000,000,000
max_requests = max(requests)
can_maximum_allocate = allocate_budget(0, M)
print(max_requests if can_maximum_allocate >= max_requests else can_maximum_allocate)