[ BOJ 2512 ] 예산(Python)

문제

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

대충 국가예산을 넘어가지 않게 상한액을 정하고,
예산 요청의 합을 구하는 문제 💰

문제 풀이

1. 이분 탐색 범위 정해주기

l, r = goal // n, max(moneys)

goal은 총 예산, n은 지방의 수다.
최솟값 l은 총 예산을 지방의 수로 나눈 값으로 해준다.
최댓값 r은 입력받은 요청 예산 중 가장 큰 값으로 해주었다.

2. 상한값 체크 함수 선언

def checking(highest_m):
    hap = sum(highest_m if highest_m < m else m for m in moneys)
    return hap

moneys 배열의 요소 중 상한값보다 큰 값이 있을 경우 상한값을 더해주고,
상한값보다 작은 값인 경우엔 그 요소를 더해주었다.

3. 함수의 리턴값으로 값 비교

if checking(mid) > goal:
    r = mid - 1
else:
    answer = max(answer, mid)
    l = mid + 1

만약 함수의 리턴값이 목표 예산보다 크면, r을 줄여준다.
(r 감소 = mid 값 감소 = 상한값 감소)

만약 리턴값이 목표 예산과 같거나 더 작으면
현재 상한값을 answer 변수와 비교해서 더 큰 값을 넣어준다.
그리고 l을 증가시켜준다.
(l 증가 = mid 값 증가 = 상한값 증가)

코드

import sys
input = sys.stdin.readline

n = int(input())
moneys = list(map(int,input().rsplit()))
goal = int(input())

def checking(highest_m):
    hap = sum(highest_m if highest_m < m else m for m in moneys)
    return hap

l, r = goal // n, max(moneys)
answer = 0
while l <= r:
    mid = (l + r) // 2
    # 더한 금액이 goal보다 같거나 크므로 상한액 줄여주기
    temp = checking(mid)
    #print("answer:{0}, mid:{1}, l:{2}, r:{3}".format(temp,mid,l,r))
    if checking(mid) > goal:
        r = mid - 1
    else:
        answer = max(answer, mid)
        l = mid + 1

print(answer)