[BOJ] 예산(2512) 문제 풀이 | Python3

---

이 문제는 이분 탐색으로 풀 수 있는 문제입니다. 

모든 요청이 배정될 수 없는 경우 가능한 최대 상한선은 입력된 지방 예산 중 최대값이므로

초기 left=1, right=max(지방예산) 으로 설정 후 이분탐색을 시작합니다. 

상한선=mid 일 때 필요한 전체 예산을 Count 함수로 계산 후 전체 예산이 국가 예산보다 크다면 해당 mid 는 불가능하고,

상한선을 작은 값으로 줄여야 하기 때문에 right=mid-1 로 변경 후 재탐색합니다.

필요한 전체 예산이 국가예산보다 작거나 같다면 해당 mid 값은 가능한 상한선 값입니다. 하지만 이보다 더 큰 상한선이 존재할 수 있으므로 현재 mid 값을 다른 변수에 저장 후 left=mid+1 로 변경 후 더 큰 mid 값에 대해 재탐색 합니다. 

 

n=int(input())
budgets=list(map(int,input().split()))
country=int(input())
 
# 상한성=mid 일때 필요한 전체 예산
def Count(mid):
    total=0
    for budget in budgets:
        if budget <= mid: total+=budget
        else: total+=mid
    return total
 
 
# 모든 요청 배정될 수 있는 경우 
if country >= sum(budgets): print(max(budgets))
# 그렇지 않은 경우
else:
    left=1; right=max(budgets)
    while left <= right:
        mid=(left+right)//2
        # 상한선=mid 일때 필요한 전체 예산이 국가 예산보다 같거나 작으면 저장 후 left 옮겨 더 큰 상한선 탐색
        if Count(mid) <= country:
            res=mid
            left=mid+1
        else: right=mid-1 # 필요예산이 국가예산보다 크면 right 줄여 상한선 금액 줄여 탐색
    print(res)