[코딩테스트] 예산

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

문제 풀이 전에 할 말

해당 문제는 이전의 랜선 자르기, 나무 자르기 문제와 매우 비슷한 성격을 띄고있다. 따라서 이전의 두 문제를 참고하고 오면 도움이 될듯하다.

• 나무 자르기: https://velog.io/@18k7102dy/coding-test-fourth-1
• 랜선 자르기: https://velog.io/@18k7102dy/coding-test-fourth-2

참고로, 해당 문제도 이분 탐색을 이용해서 풀 예정이다. 사실 리스트에 없는 값을 탐색하는 유형에는 이분탐색만한게 없긴하지...

코드부터 볼까요?

import sys

input = sys.stdin.readline

N = int(input())
budget_request_list = list(map(int, input().split()))
total_budget = int(input())

start, end = 1, max(budget_request_list)

while start <= end:
    sum = 0
    mid = (start + end) // 2
    
    for budget in budget_request_list:
        tmp = budget if mid >= budget else mid
        sum += tmp
        
    if sum <= total_budget:
        start = mid + 1
    else:
        end = mid - 1

print(end)

해당 문제도 나무 자르기와 별 다를게 없다. 오히려 풀이 자체가 똑같은 수준이니 설명은 생략.