[Python] 백준 실버3 예산

문제 링크

문제 이해하기

지방의 갯수와 각 지방별 요청 예산금액, 총 예산 금액이 주어졌을때

1.가능한한 최대의 총 예산을 사용하면서

2.모든 지방의 요청대로 배정될 수 있으면 요청한 금액을 그대로 배정하고

3.요청대로 배정하기엔 총예산이 부족하다면 특정 정수 상한액 이상의 예산요청엔 모두 상한액을 배정

접근방법

• 1.완전탐색 접근 1부터 상한액을 측정하기엔 예산이 최대 100,000까지 가능하기때문에 효율 떨어짐

  • 이분탐색

    이분탐색으로 예산 상한액의 범위를 줄여나가며 찾으면 log(n)으로 시간복잡도를 줄일 수 있음

코드구현

N=int(input())
req=list(map(int,input().split()))
M=int(input())

lo=0
hi=max(req)
mid=(lo+hi)//2
ans=0
def is_possible(mid):
    """상한금액을 파라미터로 받았을때 
    각 지방마다 얼마를 줄지 
    그때의 국가총예산이 mid와 비교해서 미만인지 초과인지 판단 """
    total=0
    for r in req:
        total+=min(r,mid)
    
    return total<=M

while lo<=hi:
    #print(f"lo:{lo} hi:{hi} mid:{mid} ans:{ans}")
    if is_possible(mid):
        lo=mid+1 #가능하다면 상한액 증가
        ans=mid
    else:
        hi=mid-1
    mid=(lo+hi)//2 #mid값 새로운 기준으로 갱신

print(ans)