예산 (python)

입력 값이 큰 경우, 이분탐색 중 최대값 구하는 문제

👀 깃헙 소스

문제설명
각 지방에서 요청하는 예산이 담긴 배열 budgets과 총 예산 M이 매개변수로 주어질 때, 위의 조건을 모두 만족하는 상한액을 return 하도록 solution 함수를 작성해주세요

입출력 예

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150일 때, 상한액을 127로 잡으면 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 됩니다.

budgets			M	return
[120, 110, 140, 150]	485	127

솔루션

가능한 n을 탐색한다.
가능한 경우는 배당 되는 예산(예산과 n 중의 작은 값)들의 합이 M보다 크거나 같은 경우이다
가능한 경우 left = middle로 업데이트 해주고.
불가능한 경우 left 값을 middle - 1로 업데이트 해준다.

코드

# 파이썬
def is_poss(middle, budgets, M):
    return M >= sum([min(middle, budget) for budget in budgets])

def solution(budgets, M):
    left, right = 1, max(budgets)
    while left < right:
        middle = (left + right + 1) // 2 
        if is_poss(middle, budgets, M):
            left = middle
        else:
            right = middle - 1
    return right