[Python] 백준 2512번 : 예산

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

2512번: 예산

---

 문제 풀이 

이진 탐색 문제이다.

 

최대 경우의 수가 10,000에 시간제한 1초로 이진 탐색을 쓰지 않으면 무조건 시간 초과가 난다.

오른쪽 값은 문제에서 원하는 상한액을 의미한다.

보통 이진 탐색 알고리즘은 정렬된 값 중에서 원하는 값을 찾는데 쓰인다.

하지만 여기선 이진 탐색으로 상한액을 조정해 예산을 계산한다.

예산이 크면 기준값을 줄이고 예산이 작으면 기준값을 올려주면 된다.

 느낀 점

이분 탐색 알고리즘 자체는 빠삭한데... 이런 식으로 사용할 수 있다는 것을 생각하지 못하였다.

처음에는 가장 작은 상한액(M을 N으로 나눈 몫)부터 따져보면 된다고 생각했다.

정렬된 배열을 탐색해서 처음 상한액보다 큰값이 나오는 구간의 idx를 따서

배열의 길이에서 그 위치를 뺀 길이 만큼 상한액을 곱하고 나머지는 더해서

M을 초과하는지 따지려고 했다.

N 자체는 10,000까지지만 상한액을 따지는 과정에서 값이 1만큼 올라가서 시간 초과가 나온 것 같다.

 코드

import sys

N = int(sys.stdin.readline())
budget = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
budget.sort()

def binary(budget):
    left, right = 0, max(budget)
    while left <= right:
        mid, sum_ = (left + right) // 2, 0
        for num in budget: 
            sum_ += min(mid, num)
        if sum_ > M: right = mid - 1
        else: left = mid + 1
        
    return right

print(binary(budget))