[백준 - 2512] 예산 - Java

문제 설명

 

2512번: 예산

 

소스 코드

import java.util.Arrays;
import java.util.Scanner;

class Main {

    static int[] budgets;

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        budgets = new int[n];
        for (int i = 0; i < n; i++) {
            budgets[i] = sc.nextInt();
        }

        Arrays.sort(budgets);

        int m = sc.nextInt();

        int start = 0, end = budgets[n - 1];
        int limit = (start + end) / 2, sum;
        while (start <= end) {

            sum = getTotalBudget(limit);

            if (sum == m) {
                break;
            } else if (sum < m) {
                start = limit + 1;
            } else {
                end = limit - 1;
            }

            limit = (start + end) / 2;

        }

        System.out.println(limit);
    }

    public static int getTotalBudget(int limit) {
        int sum = 0;

        for (int budget : budgets) {
            if (budget > limit) {
                sum += limit;
            } else {
                sum += budget;
            }
        }

        return sum;
    }
}

 

풀이 회고

해당 문제는 "이진 탐색"을 이용하여 해결할 수 있었습니다. 문제에서 요구하는 것은 "총 예산을 M을 넘지 않으면서 최대한 가깝게 만들 수 있는 상한 금액"을 구하는 것입니다. 이를 위해 문제에 접근한 방식으로는 주어진 지방의 예산액들을 기반으로 "어떤 상한액을 설정"하고 그 상한액에 따라 총 예산을 구하면서(상한액을 변경하면서) M을 넘지 않으면서 최대한 가깝게 만들어가는 것이었습니다.

 

이때 특정 상한액으로 구한 총 예산이 M 보다 작으면 상한액을 늘리고, M 보다 크다면 상한액을 줄이면 될 것입니다. 이때 단순히 1씩 증감시켜주어도 문제는 해결할 수는 있겠지만 이러한 방식은 매우 비효율적이며 1초라는 시간 제한을 초과하게 될 것입니다. 문제에서 주어진 지방의 수는 3 이상, 10,000 이하이며, 지방마다 요청할 수 있는 최대 예산 금액은 1 이상, 100,000 이하입니다. 이때 최악의 경우에는 상한액을 (대략) 10만 번 바꾸고 매번 바꿀 때마다 1만 번(지방의 수만큼)의 덧셈 연산을 해줘야하는데 그 외 연산까지 포함하면 총 10억번의 연산을 상회할 수 있기 때문입니다.

 

즉, 최소한의 상한액 변경으로 총 예산이 M을 넘지 않으면서 최대한 가깝도록 해야하며, 이 경우 "이분 탐색"을 사용하는 것이 적절합니다. 이분 탐색을 위해 입력받은 지자체의 예산 배열을 오름차순으로 정렬시켜주었습니다. 그리고 시작점(start)은 0으로, 끝점(end)은 지자체 중 최대 예산 금액으로 초기화시켜주었는데 끝점은 그렇다 치고 시작점을 지자체 중 최소 예산 금액이 아닌 0으로 설정한 이유는 지자체의 수에 따라 상한 금액이 지자체 중 최소 예산 금액 보다도 적을 수도 있기 때문입니다. 이후 이분 탐색의 중간점이자 상한 금액인 limit에 값을 할당하고 while 반복문을 통해 시작점이 끝점을 초과하기 전까지 이분 탐색을 수행하도록 했습니다.

 

        int start = 0, end = budgets[n - 1];
        int limit = (start + end) / 2, sum;
        while (start <= end) {
        
        	// TODO
        
        }

 

이제 탐색 "검증"을 위해 이분 탐색의 중간점이자 상한 금액인 limit에 따른 총 예산(getTotalBudget(limit))을 구하고 이를 sum에 할당시켜 M과 일치하는지, M 보다 작은지, M 보다 큰 지를 검증하도록 했습니다. 만약 M과 일치하면 더 이상 탐색할 필요가 없으므로 그 시점의 상한 금액(limit)을 그대로 반환시키면 됩니다. 하지만 M 보다 작으면 상한액을 더 늘려야 하므로 시작점을 중간점(limit) 보다 1 더 큰 수를 할당시켜주고, M 보다 크면 상한액을 줄여야 하므로 끝점을 중간점(limit) 보다 1 더 작은 수를 할당시켜주었습니다.

 

        while (start <= end) {

            sum = getTotalBudget(limit);

            if (sum == m) {
                break;
            } else if (sum < m) {
                start = limit + 1;
            } else {
                end = limit - 1;
            }

            limit = (start + end) / 2;

        }

 

이런 식으로 이분 탐색을 수행하다가 결국에 start가 end를 초과하게 되는데, 만일 이 지경(?)까지 와서 총 예산이 M과 일치하지 않았었다면 최종적으로 구한 상한 금액(limit)에서 현재 총 예산(sum)이 M을 넘지 않으면서 최대한 가까운 금액이 됩니다. 물론 그 전에 break를 통해 while문이 종료되었다면 총 예산(sum)이 M과 정확히 일치하는 금액일 것입니다.

 

 

의문 사항

위에서 최종적으로 즉, 이분 탐색이 끝까지 수행되어 종료될 때(start > end) 이분 탐색 시 중간점 역할을 하는 상한 금액에 의해 구해진 총 예산은 M을 넘을 수 없었습니다. 문제 요구 조건은 충족했지만 "이분 탐색으로 어떻게 항상 이 결과가 나오는지에 대한 정확한 매커니즘"은 아직 잘 모르겠습니다. 이분 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색합니다. 이 과정에서 총 예산이 M에 거의 근접해 갈 때 즈음 M 보다 커졌다가 작아졌다가를 반복하면서 최종적으로 start > end 되는 시점에 결국 M 보다 작은 결과의 상한 금액(limit)이 나옵니다. 이에 대한 예시는 다음과 같습니다.

 

4
120 110 140 150
485
limit : 75 -> sum : 300 | start : 0, end : 150

limit : 113 -> sum : 449 | start : 76, end : 150

limit : 132 -> sum : 494 | start : 114, end : 150

limit : 122 -> sum : 474 | start : 114, end : 131

limit : 127 -> sum : 484 | start : 123, end : 131

limit : 129 -> sum : 488 | start : 128, end : 131

limit : 128 -> sum : 486 | start : 128, end : 128 -> start = 128, end = 127(while문 종료 조건 충족) -> limit = 127

 

limit : 127 -> sum : 484

 

사실 while문이 다 종료되기 직전에 테스트 예제에서의 기댓값 127(M을 넘지 않으면서 가장 가까운)은 이미 등장했었습니다. 하지만 while문 종료 조건(start > end)이 충족되지 않았기 때문에 다시 이분 탐색을 하게 되는데, 결론적으로 while문이 종료될 때 기댓값 127로 다시 회귀하는 것을 확인할 수 있습니다. 막상 이분 탐색으로 구현을 해보니 문제 요구 조건을 충족하긴 했지만 이분 탐색 종료 시 "어떻게(예를 들어 어떤 수학적인 논리에 의해 등) 항상" M을 넘지 않으면서 가장 가까운 총 예산을 만드는 상한 금액이 나오게 되는지 아직 의문("M 보다 클 수는 없는 걸까?" 등)입니다.

 

 

참고자료

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