https://www.acmicpc.net/problem/2512
대충 국가예산을 넘어가지 않게 상한액을 정하고,
예산 요청의 합을 구하는 문제 💰
l, r = goal // n, max(moneys)
goal
은 총 예산, n
은 지방의 수다.
최솟값 l
은 총 예산을 지방의 수로 나눈 값으로 해준다.
최댓값 r
은 입력받은 요청 예산 중 가장 큰 값으로 해주었다.
def checking(highest_m):
hap = sum(highest_m if highest_m < m else m for m in moneys)
return hap
moneys 배열의 요소 중 상한값보다 큰 값
이 있을 경우 상한값
을 더해주고,
상한값보다 작은 값
인 경우엔 그 요소
를 더해주었다.
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)