백준/ Silver 3 문제 , 백준 파이썬 2512 , 예산

백준/ Silver 3 문제 , 백준 파이썬 2512 , 예산

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>

 

<문제 출처>

 

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

2512번: 예산

------------------------------------------------------------------------------------------------------------------------------

 

 

 

이진 탐색은 이전 풀이들이랑 비슷한 해결법으로 접근하면 된다.

 

 

참고로 예산 총액이 요구하는 예산들 합보다 크다면 조정해 줄필요가 없으므로

 

 

 

 

조건 문을 써주었다. 굳이 안쓰고 while 문만 바로 돌려도 정답이 나오지만

 

 

 

약간의 메모리와 시간 차이가 발생한다.

 

위에가 if 문을 안썼을때고, 밑에가 if 문을 썼을때이다.

 

아무래도 입력조건들을 조금더 빠르게 걸러주는 역할을 한다.

 

 

 

 

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

정답

 

 

 

import sys
input=sys.stdin.readline

N=int(input())
province=list(map(int,input().split()))
budget=int(input())


low, high = 0, max(province)

if sum(province)<=budget:
    print(max(province))
else:
    while low <= high :
        divide=(low+high)//2
        total=0

        for amount in province:
            if amount >= divide:
                total+=divide
            else:
                total+=amount

        if total <= budget:
            low=divide+1
        else:
            high=divide-1

    print(high)