예산

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12982

부서별로 신청한 금액 배열 d와 예산 budget이 주어질 때, 최대한 많은 부서에 물품을 지원하려면 몇 개 부서까지 지원 가능한지 구하기.

• d의 길이: 1 ~ 100
• d의 원소: 1 ~ 100,000
• budget: 1 ~ 10,000,000

처음 접근: 그리디인 건 알겠는데, 조합을 다 봐야 하나?

문제를 보자마자 "최대한 많이 지원"이라는 조건에서 그리디를 떠올렸다. 그런데 "정말 정렬만 해서 될까? 조합에 따라 결과가 달라지지 않을까?" 하는 의심이 들었다.

예를 들어 예산이 애매하게 걸치는 상황이면, 작은 금액 몇 개 대신 다른 조합을 골랐을 때 더 많이 지원할 수 있는 경우가 있지 않을까 하는 생각이었다.

왜 조합을 안 봐도 되는지 (증명 포인트)

이 의심을 풀기 위해 다음 질문에 스스로 답해봤다:

k개 부서를 지원하는 "어떤 조합"이 있고, 그 합이 budget 이하라고 하자. 이때 전체를 오름차순 정렬해서 뽑은 가장 작은 금액 k개의 합과 비교하면, 어느 쪽이 항상 작거나 같을까?

답은 항상 가장 작은 k개의 합이 더 작거나 같다는 것. 어떤 조합이든 k개를 뽑으면, 그 합은 "가장 작은 값 k개의 합"보다 작을 수 없기 때문이다 (정의상 가장 작은 값들만 모은 것이므로).

즉, k개를 예산 안에서 지원하는 게 가능하다면 → 가장 작은 k개의 합도 반드시 budget 이하다. 그래서 오름차순 정렬 후 앞에서부터 채워나가는 방식이 항상 최적해를 보장한다. 조합을 따로 탐색할 필요가 없었다.

헷갈렸던 부분: Collections.sort vs Arrays.sort

처음에 정렬 메서드로 Collections.sort를 떠올렸는데, d가 int[] 배열이라 Collections.sort는 쓸 수 없다는 걸 다시 짚었다. Collections.sort는 List 계열에 쓰는 메서드이고, 배열 정렬에는 Arrays.sort를 써야 한다.

최종 코드

import java.util.Arrays;

class Solution {
    public int solution(int[] d, int budget) {
        int answer = 0;

        Arrays.sort(d);

        for (int i = 0; i < d.length; i++) {
            if (d[i] <= budget) {
                budget -= d[i];
                answer++;
            }
        }

        return answer;
    }
}

break를 안 넣어도 되는 이유

정렬되어 있으니 예산이 부족한 원소를 만나는 순간 break로 끝내도 되지 않을까 하는 얘기가 나왔다. 실제로 넣어도 정답에는 영향 없다 (오름차순이라 이후 원소도 어차피 못 산다).

다만 d.length가 최대 100이라 최악의 경우에도 100번 도는 게 전부라, break 유무가 성능에 미치는 영향이 사실상 없다. 시간복잡도는 정렬(O(n log n))이 지배적이라 지금 코드로 충분하다.

정리

• 그리디 문제에서 "이 조합이 최선인지" 의심될 땐, 같은 개수를 뽑는 다른 조합과 비교해서 우열을 증명해보면 확신이 선다.
• 배열(int[])과 리스트(List<Integer>)는 정렬 메서드가 다르다 — Arrays.sort vs Collections.sort.
• 입력 크기가 작을 땐 이론적 최적화(break 등)보다 코드 가독성을 우선해도 무방하다.