백준(2512) - 예산 Python

백준(2512) - 예산

문제풀이: 이진탐색, 파이썬

해결방법

예시)

# 입력 #
4
120 110 140 150
485

# 출력결과 #
127

• 이진탐색의 방법과 구현이 약간 혼합된 문제이다.
• 탐색할 값을 적절히 구하는 방법만 구현하면 쉽게 풀리는 문제였다.

import sys
input = sys.stdin.readline

n = int(input())
bugets = list(map(int, input().split()))
m = int(input())
bugets.sort()
start = 0
end = bugets[-1]

answer = 0
while start <= end:
    mid = (start + end) // 2
    res = 0
    for buget in bugets:
        if buget <= mid:
            res += buget
        else:
            res += mid
    if res > m:
        end = mid - 1
    elif res < m:
        start = mid + 1
        answer = max(answer, mid)
    elif res == m:
        answer = mid
        break

print(answer)