거스름돈.md

코드

import java.util.*;

class Solution {
    public int solution(int n, int[] money) {
        Arrays.sort(money);
        int[] dp=new int[n+1];
        dp[0]=1;
        
        for(int i=0; i<money.length; i++){
            for(int j=money[i]; j<=n; j++){
                // 새로운 j원 조합은
                // 이전 j원 조합 + j-money[i]원 조합
                dp[j]=dp[j]+dp[j-money[i]];
            }
            
        }
        
        return dp[n];
    }
}