백준 알고리즘 2512번 : 예산 파이썬 코드 <문제풀이>

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

2512번: 예산

import sys;input=sys.stdin.readline
import bisect
N=int(input())
jibang=list(map(int,input().split()))
M=int(input())
psum=[ 0 for _ in range(N+1)]
jibang.sort()

s=sum(jibang)
if s < M:
    print(jibang[-1])
    sys.exit()

for i in range(1,N+1):
    psum[i]=psum[i-1]+jibang[i-1]

left,right=0,jibang[-1]
i=0
while left<=right:
    mid=(left+right)//2

    point=bisect.bisect_left(jibang,mid)
    t_sum=psum[point] + mid * (N-point)

    if t_sum>M:
        right=mid-1
    else:
        left=mid+1
            
print(right)

 

이분탐색은 꾸준한 연습이 필요한 분류의 문제라는 걸 다시한번 느꼈다.

실버 3인데도 힘들었다 -_-

그래도 최적화를 위해서 누적합을 활용했던 것은 잘한 점이다.