백준 2512 : 예산 with 파이썬 / 이분탐색

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

2512번: 예산

 

# 포인트

1. 어려운 이진탐색은 단순히 값들과 mid값들을 비교하는 게 아니라, mid를 통해 구해진 값들을 이용해 비교해준다.

여기서는 2가지 비교가 이뤄졌는데

ⓐ 가상의 예산 상한선인 mid와 그 mid를 이용해 계산된 필요한 총 예산인 result

ⓑ 가상의 총 예산인 result와 주어진 총 예산인 m

을 비교해주면 된다

 

2. result가 최대 예산인 m보다 적으면 상한선인 mid를 늘려갈 수 있다

 

n=int(input())
ns=list(map(int, input().split()))
ns.sort()
m=int(input())
answer=0
st, end=1, ns[-1]   # mid는 가상이 상한이므로 최대 ns의 최대값이 될 수 있다
while st<=end:
    mid=(st+end)//2
    result=0
    
    #ⓐ 가상의 예산 상한선인 mid와 그 mid를 이용해 계산된 필요한 총 예산인 result
    for x in ns:
        if x <= mid:
            result+=x
        else : result+=mid
        
	#ⓑ 가상의 총 예산인 result와 주어진 총 예산인 m
    if result <= m: 	# result가 최대 예산인 m보다 적으면 상한선인 mid를 늘려갈 수 있다
        answer=mid
        st=mid+1
    else : end=mid-1

print(answer)