[Python] 백준 #2512- 예산

문제

---

 

2512번: 예산

코드

---

My answer

import sys
input= sys.stdin.readline

N=int(input())
budget=list(map(int,input().split()))
target=int(input())
start,end=0,max(budget)

while(start<=end):
    mid=(start+end)//2
    tmp=sum([mid if i>=mid else i for i in budget])
    if(tmp>target):
        end = mid-1
    else:
        start = mid+1   
print(end)

 

풀이

---

이분탐색으로 해결하는 문제로, 조건을 만족하는 최대 예산을 찾아야한다. 

우선 start=0, end=예산의 최대값으로 지정해주고 이 사이의 값들을 통해 반복해나가며 최적의 값을 찾아야한다.

일반적인 이분탐색 코드를 작성하고, target과 조건을 적용했을 때의 tmp와 비교한다. 

tmp가 더 클 경우에는 상한예산을 더 작게 설정해야하므로 end를 mid-1로 구간을 줄여주고, 

tmp가 더 작거나 같을 경우에는 상한예산을 더 크게 설정해야하므로 end를 mid+1로 설정해준다.

우선 만족하는 "최대"값을 찾아야하므로 쉽게 그냥 end를 반환하면 된다고 생각했다.

조건을 만족하는 "최소"값을 찾을 때는 start를 반환.

이 문제와 같은 유형을 풀 때는 부등호, 반환값을 매우 신경써야할 것 같다.

자세한 유형들은 아래 알고리즘에서 설명해놨다. 

Algorithm 5. 이진탐색(binary search)