[프로그래머스 - Level3] 거스름돈

전체 문제 설명

문제 요약

거슬러 줘야 하는 금액 n과 현재 보유하고 있는 돈의 종류 money가 매개변수로 주어질 때, n 원을 거슬러 줄 방법의 수를 구하시오.

제한 사항

• n은 100,000 이하의 자연수입니다.
• 화폐 단위는 100종류 이하입니다.
• 모든 화폐는 무한하게 있다고 가정합니다.
• 정답이 커질 수 있으니, 1,000,000,007로 나눈 나머지를 return 해주세요.

답이 될 수 있는 경우의 수 분류

주어진 돈의 종류를 조합해서 금액 n을 만들 수 있는 경우의 수를 구하는 전형적인 dp 문제입니다.

돈의 종류가 {100, 200, 400, 600}과 같이 있다고 가정해 보겠습니다. 주어진 화폐로 어떤 금액 n을 만들 수 있는 경우의 수는, 600원이 0번 쓰이는 경우의 수부터 600원이 i번(0 <= i <= n / 600)쓰인 경우의 수로 이루어질 것입니다.
각 경우에 대해, 600원이 만약 0번 쓰였다면, 나머지 화폐인 {100, 200, 400}으로 n을 구성할 수 있는 경우의 수를 구해야하고, i번 쓰였다면 {100, 200, 400}으로 (n - i * 600)을 구성할 수 있는 경우의 수를 구해야 합니다.

이렇게 분류한 각 경우 ({100, 200, 400}으로 n - i * 600을 구성하는 경우들) 에 대해, 400원을 j번 (0 <= j <= n / 400) 쓰는 경우의 수를 구하고, 이들을 다시 200원을 k번 (0 <= k <= n / 200) 쓰는 경우의 수로 분리할 수 있습니다.

작은 단위에서 시작하기

우선, 가장 작은 단위에서 이 문제를 접근해보면, 돈의 종류가 하나인 상황을 가정해 볼 수 있습니다.

돈의 종류가 하나이고 이 화폐를 money[i]라고 할 때, 어떤 금액 amount (0 <= amount <= n) 을 만들 수 있는 경우의 수는 amount가 money[i]로 나누어 떨어진다면 1, 아니라면 0입니다.

이 가장 단순한 경우에, money[i + 1]이라는 화폐 하나를 추가해 보겠습니다. money[i + 1]을 추가적으로 고려했을 때 어떤 금액 amount를 만들 수 있는 경우의 수는, money[i + 1]이 amount를 구성하기 위해 0번 쓰인 경우부터 amount / money[i + 1]번 쓰인 경우까지 고려할 수 있습니다.

money[i + 1]이 0번 쓰인 경우는, money[i]로 amount금액 전체를 구성할 수 있는 경우와 같고, 1번 쓰인 경우는 money[i]로 amount - money[i + 1], 2번 쓰인 경우는 money[i]로 amount - 2 * money[i + 1]을 구성하는 경우의 수와 같습니다.

여기서, money[i + 2]라는 화폐가 추가되더라도, money[i]와 money[i + 1]까지 고려했을 때 amount(0 <= amount <= n)을 구성할 수 있는 모든 경우의 수를 구해놓았기 때문에, 같은 방식으로 money[i + 2]가 0번 쓰인 경우, 1번 쓰인 경우, ..., amount / money[i + 2]번 쓰인 경우를 고려해서 답을 채워나갈 수 있습니다.

답을 구하는 과정을 나타낸 그림입니다. 그림에서는 편의상 amount를 100단위로 표현하고 화폐의 종류를 임의로 설정했습니다. 각 화살표는 해당하는 칸의 값이 계산되기 위해 참조해야하는 칸들을 가리키고 있습니다. 편의상 주어진 화폐의 배수가 되는 칸에만 표시했지만, 실제로는 각 행의 모든 열에 대해서 같은 종류의 계산이 이루어집니다.

여기서 한가지 비효율적인 부분은, 새로운 화폐인 money[i]를 0개부터 amount / money[i]까지 넣는 과정을 매 칸마다 시뮬레이션 한다는 점입니다.
그림에서 {100, 300}원만을 고려해서 600원을 만들 수 있는 경우의 수를 계산하는 부분을 살펴보면 계산의 중복이 발생함을 알 수 있습니다.(그림의 2행 7열)

300원을 2개 포함해서 600원을 만드는 경우의 수(100원만으로 0원을 만드는 경우의 수), 300원을 1개 포함해서 600원을 만드는 경우의 수(100원만으로 300원을 만드는 경우의 수의 합은 이미 2행 4열에 구해져 있습니다. 새로 구해야하는 부분은 오직 300원을 0번 사용해서 600원을 만드는 경우의 수(100원만으로 600원을 만드는 경우의 수, 1행 7열) 뿐입니다.

따라서, money[0]부터 money[i]까지 고려했을 때 amount를 구성할 수 있는 경우의 수를 그림의 테이블과 유사하게 dp[i][amount]라고 표현할 때, 구성해야할 amount가 현재 고려중인 화폐 money[i]보다 같거나 큰 경우에는, money[i]를 0번 써서 amount를 구성할 수 있는 경우의 수인 dp[i - 1][amount]와 money[i]를 1번부터 amount / money[i]번 써서 구할 수 있는 경우의 수의 합인 dp[i]amount - money[i]]를 더한 값만 계산하면 됩니다.

계산 중복을 해결한 것만으로도 충분하지만, 금액이 최대 100000이고, 화폐 종류가 최대 100가지이므로, 100000 * 100 * 4 byte짜리 배열을 생성하고 싶지 않다면, 2차원 배열을 선언하는 대신 1차원 배열로 문제를 해결할 수 있습니다. 결국 dp[i][j]에서 계산하는 값은 dp[i - 1][j] + dp[i]j - money[i]]입니다.

만약 화폐 종류별로 열을 따로 두지 않고, 배열을 한 줄만 쓴다면, dp[j]의 값을 갱신하기 전에는 2차원 배열에서의 dp[i - 1][j]을 지니고 있을 것이므로,
dp[j] += dp[j - money[i]]를 구하면 2차원 배열을 사용했을 때와 같은 값을 얻을 수 있습니다.

코드

import java.util.*;
class Solution {
    public int solution(int n, int[] money) {
        int mod = 1_000_000_007;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for(int m : money){
            for(int amount = 0; amount <= n; amount++){
                if(amount >= m){
                    dp[amount] += dp[amount - m];
                    dp[amount] %= mod;
                }
            }
        }
        return dp[n];
    }
}