2512번 예산

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

아이디어

앞서 풀었던 1654번 랜선 자르기와 아주 비슷한 문제였다.

이분탐색으로 예산 이하 중 가장 큰 값을 찾으면 된다.

예산 이하의 값이 나올 때마다 answer에 갱신해주면서 진행했다.
WHY? 예산 이하의 값이 나오면 어차피 low = mid+1을 해주어 또 확인하기 때문에0 현재 answer보다 더 큰 값이 나오거나 그 자체가 정답이기 때문

코드

n = int(input())
request = list(map(int, input().split()))
budget = int(input())

low = 1
high = max(request)
answer = 0

while low <= high:
    mid = (low + high) // 2
    sum = 0
    
    for num in request:
        if num >= mid:
            sum += mid
        else:
            sum += num

    if sum <= budget:
        answer = mid
        low = mid + 1
    else:
        high = mid - 1
        
print(answer)