231209 거스름돈

private static final int MOD = 1000000007;

public int solution(int n, int[] money) {
    Arrays.sort(money);

    int[] dp = new int[n + 1];
    dp[0] = 1;

    for (int coin : money) {
        for (int amount = coin; amount <= n; amount++) {
            dp[amount] = (dp[amount] + dp[amount - coin]) % MOD;
        }
    }

    return dp[n];
}

출처:https://school.programmers.co.kr/learn/courses/30/lessons/12907