백준 2512번
국가에서는 여러 지방에서 요청한 예산을 최대한 지급하려 한다. 하지만 국가의 총 예산이 제한되어 있기 때문에, 총 예산을 넘지 않는 선에서 요청 예산을 지급하기 위해 "상한액"을 정하여 상한액을 넘는 요청인 경우 상한액을 지급하기로 한다. 이 때, 배정된 예상 중 최대값을 프린트한다.
N = int(input())
max_range = 0
money_list = []
for money in input().split(" "):
money = int(money)
max_range = max(money, max_range)
money_list.append(money)
deposit = int(input())
if sum(money_list) <= deposit:
print(max_range)
else:
condition = True
small_range = int(deposit/N)
max_range = min(max_range, deposit)
while(condition):
expectation, total = int((small_range + max_range)/2), 0
for money in money_list:
if money < expectation:
total += money
else:
total += expectation
if (total == deposit):
condition = False
elif total < deposit:
small_range = expectation
if max_range - small_range < 2:
condition = False
elif total > deposit:
max_range = expectation
print(expectation)
이분 탐색으로 잘 풀었지만, 코드의 가독성을 높힐 필요가 있다.
1. while(left <= right):
로 작성하자. 해당 구문을 사용하면 다른 작성자가 이분 탐색을 사용했구나 하고 읽기가 편하다.
2. middle = (left + right) // 2
3. left = middle + 1 또는 right = middle - 1 을 사용하여 무한 루프가 도는 것을 방지하자.