[테스트케이스 추가] 백준 2512번: 예산 python, 파이썬

1. 문제

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

2512번: 예산

 

 

2. 풀이

binary search

 

 

3. 구현

import sys
# sys.stdin = open('input.txt')

n = int(sys.stdin.readline())
lis = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())

le=0
ri=max(lis)
sum=0
while le<=ri:
    mid = (le+ri)//2
    sum=0
    for item in lis:
        sum +=min(item, mid)
    if sum>m:
        ri=mid-1
    else:
        le=mid+1
# print(sum)
print(ri)

 

 

 

4. 테스트케이스 추가

8
110 150 74 112 54 144 56 112
480

답: 61

 

6
77 89 61 118 91 142
120

답: 20