거스름돈

function solution(n, money) {
    const MOD = 1000000007;  // 나머지
    
    const MONEY_NUM = money.length;
    const DP_NUM = n + 1;
    
    const dp = new Array(DP_NUM).fill(0); // DP 저장할 배열
    
		// 일종의 점화식을 만들어서 주어진 문제를 단순화시켜서 값을 저장하여 해결하는 것
		// 거스름돈이 만들어지는 경우의 수
    // n = 5 money=[1,2,5] => 5원은 어떻게 만들어지지?
    // dp[5] = dp[4]에서 만들어지겠네(1원일 때)
    // dp[3] 1에서 만들어지겠네. => dp[n] = dp[n - money]

    // 이상한 식을 만들었는데, 이게 되나 검증해야 함
    // dp[3] = 1 (m = 2) / 2 (m = 1) - 겹치는 상황이 발생
    // dp[2] = 1 1

		// 어 겹치는 상황은 배제해야 하네!
    // 머니를 쭉~돌립니다 [1,0,0,0,0,0] [1,1,1,1,1,1]
    // [1,1,2,2,3,3]
    // [1,1,2,2,3,4]
    dp[0] = 1;
    
    for (let i = 0; i < MONEY_NUM; i += 1) {
        const m = money[i];
        
        for (let idx = 0; idx < DP_NUM; idx += 1) {
            const diff = idx - m;
            
            if (diff >= 0) {
                dp[idx] += dp[diff] % MOD
            }
        }
    }
    
    return dp[n] % MOD
}