미소를뿌리는감자의 코딩
[백준 2024/02/24] 2512번 예산 본문
728x90
https://www.acmicpc.net/problem/2512
1. 접근 방법
이 예제를 예로 들어서 설명을 해볼 것이다.
국가예산의 총액이 485 이므로, 총 지방 예상의 예산 요청 수(4)로 나눈다.
이걸 하기로 한 이유는, 예산 요청과 관계 없이, 국가 예산이 다른 지방 예산들에게 나누어 줄 수 있는 예산의 최대값을 구해보고 싶었기 때문이다.
486/4 = 121.25 이다. 평균보다 지방 예산 요청이 낮은 경우, 120, 110은 afford 할 수 있다고 판단했기 때문에, 요청한 지방 예산 그대로를 주기로 판단하였다.
따라서 485 - 120 - 110 = 255. 이제 255 예산이 남게 된다.
-- 재귀
이제 여기서 위에서 반복 했던 것을 다시 한다.
남아 있는 예산 255 / 2 를 하게 되면, 127.5 이다. 이 값보다 어떠한 값도 작은 값이 없다. [140, 150] 이 남아 있으므로,, 따라서 afford 할 수 없다고 판단이 되게 된다.
이 때는 127.5가 나누어줄 수 있는 예산의 최댓값이 된다. 정수 상한액을 구해야 하므로, (int)127.5 를 반환해 주었다.
물론 이러한 계산이 가능한 것은, 지방 예산 요청의 합이 지방 예산의 총액보다 같거나 작을 때는
요청한 금액을 그대로 배정하면 되므로, 요청한 금액 중 제일 높은 값을 반환을 해주었다.
이 부분이 선행 되어서 판단을 하고 난 후, 지방 예산 요청이 예산의 총액보다 높을 때에는 위에서 언급한 계산들을 해주었다.
2. 코드
def budget(requests, limit_budget):
avg = limit_budget / len(requests)
revisit = []
assigned = []
for request in requests:
if request <= avg:
limit_budget -= request
assigned.append(request)
else:
revisit.append(request)
if revisit == requests:
return int(avg)
return budget(revisit, limit_budget)
def check_budget_sufficient(requests, limit_budget):
if sum(requests) <= limit_budget:
return True
return False
def main():
input()
requests = list(map(int, input().split()))
limit_budget = int(input())
if check_budget_sufficient(requests, limit_budget):
print(max(requests))
else:
print(budget(requests, limit_budget))
if __name__ == "__main__":
main()
728x90
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/02/24] 1645번 랜선 자르기 (0) | 2024.02.25 |
---|---|
[백준 2024/02/25] 2805번 나무 자르기 (1) | 2024.02.25 |
[백준 2024/02/23] 2212번 센서 (0) | 2024.02.23 |
[백준 2024/02/23] 11000번 강의실 배정 (0) | 2024.02.23 |
[백준 2024/02/23] 13305번 주유소 (0) | 2024.02.23 |