[백준] 2512번 : 예산 (파이썬,pypy3)

문제

나의 첫번째 답안

n=int(input())
arr=list(map(int,input().split()))
ex=int(input())

mn,mx=0,max(arr)

while mn<=mx: #최댓값을 초과하기 전까지 반복
    mid=(mn+mx)//2#상한액 기준
    total=0#예산 총합

    for i in arr:
        if i>=mid:#상한액 기준보다 크거나 같은 요청금액에 대해
            total+=mid#더함
        else:#작다면 무조건 전액이 추가되므로 추가
            total+=i
            
    if total>=ex:#예산의 합이 예산 총액을 넘는다면
        mx=mid-1#줄여줌
    else:#아니라면
        mn=mid+1#최솟값을 늘려줌

print(mx)

if total>=ex:#예산의 합이 예산 총액을 넘는다면
        mx=mid-1#줄여줌
else:#아니라면
	mn=mid+1#최솟값을 늘려줌

해당 코드에서 예산이 같을 때는 mx값을 줄일 필요가 없으므로 조건문을 수정해주어야 했다.

나의 답안

n=int(input())
arr=list(map(int,input().split()))
ex=int(input())

mn,mx=0,max(arr)

while mn<=mx: #최댓값을 초과하기 전까지 반복
    mid=(mn+mx)//2#상한액 기준
    total=0#예산 총합

    for i in arr:
        if i>=mid:#상한액 기준보다 크거나 같은 요청금액에 대해
            total+=mid#더함
        else:#작다면 무조건 전액이 추가되므로 추가
            total+=i
            
    if total>ex:#예산의 합이 예산 총액을 넘는다면
        mx=mid-1#줄여줌
    else:#아니라면
        mn=mid+1#최솟값을 늘려줌

print(mx)#가능한 한 최대의 총 예산 출력

접근 방법

• 이분탐색 문제이다.
• 상한액보다 낮은 금액은 모두 배정이 가능하며 상한액을 넘는 금액에 대해서는 상한액까지만 배정하도록 한다.
  따라서 조건을 두개로 나누어 주어야 한다.
• 예산의 합이 국가예산의 총액을 초과하는지 아닌지에 따라 상한액을 조절해주면 된다.