[2512] 예산 in python [이분탐색]

전형적인 이분 탐색 문제!

오랜만에 풀었던 탓인지

이분 탐색 구현하는 데 있어서 사알짝 버벅..버벅..거렸다..

(열심히 하자..)

 

 

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다. 

 

여러번의 실패를 경험한 가장 중대했던 이유

start의 초기값을 0으로 설정해뒀기 때문 ^^

 

 

다시 정리해두자!

 

(1) 초기값 설정

- start=0

- end=max(리스트)

 

(2) 반복문 조건 설정

while start<=end

: start의 값이 end 값을 넘어가는 순간 반복문이 종료되게끔!

 

(3) 중간값 설정

mid = (start+end)//2

 

 

n=int(input())
array=list(map(int,input().split()))
m=int(input())

start=0
end=max(array)
mid=0

while start<=end:
    temp=0
    mid = (start + end) // 2
    for num in array:
        if num<mid:
            temp+=num
            continue
        temp+=mid
    if temp<=m: # 주어진 값보다 작다면, 정수 상한액을 높여줘야한다.
        start=mid+1
    else:
        end=mid-1
print(end)