[백준알고리즘] 2512번: 예산 -Python

[백준알고리즘] 2512번: 예산 -Python

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

2512번: 예산

상한액보다 많은 예산을 요구하면 상한액까지만 지급하고 상한액보다 낮은 예산을 요구하면 모두 지급하면 된다. 이 총액이 주어진 총 예산보다 낮거나 같은 최대의 상한액을 구하면 된다.

 

이분 탐색으로 풀어주었다. 다양한 조건들로 이분 탐색을 할 수 있어서 계속 헷갈린다..

 

아래의 두 코드는 같은 코드인데 이분탐색 부분만 조금 차이가 있다.

import sys

n = int(sys.stdin.readline())
budget = list(map(int, sys.stdin.readline().split()))
total = int(sys.stdin.readline())
lo, hi = 0, max(budget)

while lo != hi: # lo == hi면 해당 상한액이 최대 상한액
    mi = (lo + hi + 1)//2
    tmp = sum(map(lambda x: x if x < mi else mi, budget))
    if tmp > total:
        hi = mi-1	# mi가 상한액이 될 수 없기 때문에 범위에서 제거
    elif tmp < total:
        lo = mi		# mi가 상한액이 될 수 있기 때문에 범위에 포함
    else:
        lo = hi = mi	# mi가 상한액임
print(hi)

아래의 코드는 lo > hi가 되는 부분이 lo = mi+1에 의한 것인지 hi = mi-1에 의한 것인지에 따라서 최대 상한액이 결정될 수 있다.

import sys

n = int(sys.stdin.readline())
budget = list(map(int, sys.stdin.readline().split()))
total = int(sys.stdin.readline())
lo, hi = 0, max(budget)

while lo <= hi: # lo가 hi보다 커지면 멈춤
    mi = (lo + hi)//2
    tmp = sum(map(lambda x: x if x < mi else mi, budget))
    if tmp > total:	# mi가 상한액이 될 수 없기 때문에 범위에서 제거
        hi = mi-1	# lo == hi이더라도 hi가 상한액이 될 수 없으면 하나 전의 값이 상한액
    elif tmp <= total:	# mi가 상한액이 될 수 있으나 mi보다 큰 범위에서 탐색
        lo = mi+1
print(hi)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다