[백준/Python]2512_예산

문제

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

2512번: 예산

풀이

이분 탐색을 이용하여 풉니다.

n개의 예산 요청액들을 moneys 리스트에 저장하고 이분 탐색의 탐색 범위는 0부터 max(moneys)까지 입니다.

이분 탐색 반복문을 돌면서 총 예산 합(result)이 최대 예산(m)을 넘지 않으면서 가장 큰 값이 될 때의 최대 상한액(limit)을 구합니다.

코드

import sys


def binary_search(left, right):
    result = 0  # 총 예산 합
    limit = 0  # 최대 상한액
    while left <= right:
        mid = (left + right) // 2
        total = 0
        for money in moneys:
            if money > mid:
                total += mid
                continue
            total += money
        if total <= m:
            if result <= total:
                result = total
                limit = mid
            left = mid + 1
            continue
        if total > m:
            right = mid - 1
    return limit


n = int(sys.stdin.readline().rstrip())
moneys = list(map(int, sys.stdin.readline().rstrip().split()))
m = int(sys.stdin.readline().rstrip())
print(binary_search(0, max(moneys)))