[백준] 2512 - 예산

문제 링크 : https://www.acmicpc.net/problem/2512

코드

import sys

def get_amount(requests, upper):
    amount = 0
    for req in requests:
        amount += min(req, upper)
        
    return amount

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

left, right = 1, max(requests)
answer = 1
while left <= right:
    mid = (left + right) // 2
    amount = get_amount(requests, mid)
    if amount < m:
        answer = max(answer, mid)
        left = mid + 1
    elif amount == m:
        answer = mid
        break
    else:
        right = mid - 1
        
print(answer)

풀이

각 지방의 예산요청의 총합이 총 예산을 넘지 않는 조건 하에서 상한액의 최댓값을 구해야 한다.

각 지방 예산 요청의 최솟값은 1이므로 상한액의 최솟값도 1로 잡는다. 또한 상한액의 최댓값은 총 예산과 같게 잡는다. (지방 단체의 최소 개수가 3이므로 엄밀히는 '총 예산//3'으로 잡아야 하겠지만 이분 탐색을 활용하므로 이 문제에서는 연산 횟수 상 유의미한 차이는 없다고 생각한다)

상한액의 최솟값, 최댓값을 각각 left, right에 할당한 후 중간값을 구한다. 이때 문제 조건에 따라 상한액을 고려하여 각 지방 단체에 할당된 예산의 총합을 구한다.
이 총합이 총 예산보다 작다면 상한액을 더 높여도 된다는 뜻이므로 mid+1이 left로 변한다.
반대의 경우는 right로 변한다.
그 외에 총 예산과 같다면 그때가 최적의 지점이므로 while문을 break한다.

근거

총 예산을 나타내는 정수 M은 1,000,000,000 이하이다. 거기에 지방 단체의 수 N은 최대 10,000이므로 1~1,000,000,000의 수를 하나하나 탐색하면서 각각의 경우에 10,000개의 연산을 수행한다면 엄청난 수의 연산을 수행해야 한다.

때문에 1~1,000,000,000 사이의 수를 탐색하는 방식을 'binary search'로 선택해야 한다. 2^10이 대략 1000이라고 rough하게 가정한다면 1~1,000,000,000 범위의 수를 탐색하는 데에는 약 30번의 연산만이 필요하다. (2^10은 엄밀하게는 1024이므로 30번보다 더 적은 횟수의 연산이 필요할 것이다.)