[백준] 2512번 : 예산 (JAVA)

인간몽쉘김통통·2024년 1월 5일

백준 알고리즘 이분 탐색

백준

목록 보기

41/92

문제

이해

N개의 지방이 존재하는데 각 지방에 따라 필요한 예산이 정해져 있다.

국가가 지방들에게 예산을 분배하려고 한다. 총 예산은 한정되어 있다.

각 지방에게 최대한 많은 예산을 분배하려고 할 때 다음과 같은 분배 규칙을 따른다.

모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.

모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.

2번이 이해하기 어려울 수 있다. 예산이 요청한 것에 비해 부족할 때 분배 상한액을 결정한다.

분배상한액 이하의 예산을 원하는 지방에는 요청한 예산을 그대로 배정하고

초과하는 지방에는 분배상한액 만큼 배정한다는 의미이다.

접근

문제는 간단해보이지만 조금 헷갈릴 수 있는 부분이 있었다.

분배규칙 1의 경우처럼 예산이 넉넉하다면 단순히 원하는 만큼 배정해주면 되지만 분배규칙 2의 경우처럼 조금 복잡해지는 상황이 발생한다.

나는 상한액이 모든 지방에 공통적으로 적용된다는 점을 생각하여 예산의 평균액을 떠올렸다.

예산을 최대로 나누어준다고 했을 때 각 지방에게 평균치 만큼 나누어주면 총 예산에 딱 떨어지기 때문이다.

하지만 지방마다 요청 예산은 다르기 때문에 분배 평균보다 낮은 지방과 높은 지방이 존재할 수 있다.

평균보다 낮은 지방은 어떻게 처리하면 될까? 단순하게 평균보다 낮기 때문에 요청한 만큼 예산을 나누어주면 된다.

높은 지방은 어떻게 처리하면 될까? 높은 지방은 딱 평균만큼 배정하고 부족한 금액을 다시 저장한다.

이러한 방식으로 모든 지방을 돌아 예산을 배정하면 어떠한 결과가 나올까?

3가지의 경우가 존재할 수 있다.

모든 지방의 요청 예산이 0 : 끝 (더 이상 나눠줄 필요 없으므로 이 때의 최댓값은 지방 중 최대 요청 예산 값이 된다.)
요청 예산이 0인 지방과 아닌 지방이 혼재
모든 지방의 요청 예산이 존재 : 끝 (총 예산이 부족하기 때문에 최댓값은 나눠주는 평균값이 된다.)

1번과 3번의 경우 처리가 단순하다. 특수한 만큼 상황을 종료하면 된다. 하지만 2번의 경우에는 배정 전과 다를게 없다.

그렇기 때문에 2번의 경우에는 다시 한번 평균 예산만큼 배정하면 된다.

요청 예산이 0인 지방은 모두 삭제하고 남아있는 지방에 현재 남아있는 예산의 평균값을 다시 배정한다.

이를 통해 다시 이전의 과정을 거쳐서 최종적으로는 예산이 부족하거나 요청 예산이 없는 1번과 3번의 결과로 귀결된다.

위 알고리즘은 예제 1에 적용시켜 보자.

루프 1	120	110	140	150	배정금액	소비 예산
	0	0	19	29	121	475

루프 2	0	0	19	29	배정금액	소비 예산
	0	0	6	6	6	484

루프 3	0	0	13	23	배정금액	소비 예산
	0	0	0	0	0	484

최종적으로 루프3을 보면 남은 예산이 1, 따라서 배정할 수 있는 금액은 0이기 때문에 총 예산이 부족하다는 3번의 경우가 발생하게 된다.

따라서, 최종적으로 소비한 예산인 484가 최대 배정 금액이 된다.

코드

package java_baekjoon;

import java.util.*;
import java.io.*;

public class prob2512 {
    static int N;
    static Queue<Integer> q;
    static int budget;
    static int ans = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        q = new LinkedList<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            q.add(Integer.parseInt(st.nextToken()));
        }

        budget = Integer.parseInt(br.readLine());

        while (!q.isEmpty()) {
            int qsize = q.size();
            int avg = budget / qsize;
            if(avg == 0){
                break;
            }
            int allocated_budget = 0;
            for (int i = 0; i < qsize; i++) {
                int need = q.poll();

                if (need <= avg) {
                    if(need > allocated_budget){
                        allocated_budget = need;
                    }
                    budget -= need;
                } else {
                    if(avg > allocated_budget){
                        allocated_budget = avg;
                    }
                    budget -= avg;
                    q.add(need - avg);
                }
            }
            ans += allocated_budget;
        }

        System.out.println(ans);

        return;
    }
}