[BinarySearch] 예산

랜선자르기와 비슷한 유형의 문제

 

_ = int(input())
array = list(map(int, input().split()))
max_budget = int(input())

start = 0
end = max(array)

while start <= end:
    mid = (start + end) // 2 
    our_budget = []
    for x in array:
        our_budget.append(min(x, mid))
        
    if sum(our_budget) > max_budget: 
        end = mid - 1
    else:
        start = mid + 1

print(end)
# start = 128, end = 127로 종료된다

여기서도 최대를 찾는 것이기 때문에

랜선 자르기 문제처럼 end지점이 찾고자 하는 값이다.

our_budget을 리스트로 만들었는데 그냥 0으로 할당하고 매번 더해도 상관은 없다.

디버깅 하면서 리스트 보고 싶어서 만들었음.

 

검색하다보니 min으로 x와 mid를 비교하면 코드가 더 간단해진다는 것을 깨달음.