[백준 2512 파이썬] 예산 풀이

문제

 

 

-줄 수 있는 예산의 총액이 이 주어지고 그 총액이 넘지 않는 선에서 각 지방에 최대한으로 공급하고 한다.

 

입력

첫째줄에는 지방수

둘째 줄에서는 각 지방이 요청하는 예산

셋째 줄에는 총예산

 

출력

각 지방에 배정될 예산중 최대를 출력한다

 

풀이

가능한 예산값 v를 1부터 해서 증가해서 각 지방이 요청한 값보다 크면 그 지방이 요청한 값을 예산으로 정하고

작으면 v로 하여 총예산 보다 작은지 큰지 확인하면서 가능한 v의 최댓값을 구할 수 있다 다만 이렇게 하면

이 문제에서는 시간 초과로 나오기에 이분탐색 방법을 사용하여 좀 더 빠르게 구할 수 있다

 

이분탐색은 변수 s에 0을 변수 e에 지방이 요청하는 예산중 가장 큰 값으로 하여

 (s+e)//2 중간값을 구하여 그 값을 기준으로 위의 과정을 돌려 총예산보다 작은지 큰지 확인하다

만약 총예산 보다 크다면 e의 값을 현재 구한 중간값 보다 작게 해 다시 확인하게 하고

만약 총예산 보다 작다면 중간값을 크게 하기 위해 s의 값을 중값보다 크게 잡아 다시 확인한다

 

코드

n=int(input())
data=list(map(int,input().split()))
m=int(input()) #총예산

start=0
end=max(data)

while start<=end:
    mid=(start+end)//2 
    value=0 #총예산하고 비교할 값

    for i in data:
        if i <=mid:
            value+=i
        else:
            value+=mid

    if value>m: #총예산보다 큼으로 값을 줄이기위해 end값을 감소시킨다
        end=mid-1
    else:
        start=mid+1

print(end)