[백준 2024/02/24] 2512번 예산

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

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()