거스름돈

import java.util.*;
class Solution {
    
    public int solution(int n, int[] money) {
        int answer = 0;
        int[] arr = new int[n+1];
        Arrays.sort(money);
        
        arr[0] = 1;
        for(int m : money){
            for(int i=m;i<=n;i++){
                arr[i] += arr[i-m];
            }
        }
        answer = arr[n];
        return answer;
    }
}

n원을 만드는 방법의 수는 기존 n원을 만드는 방법의 수 + (n-money)원을 만드는 수이다.

 

초기     1 0 0 0 0 0
n = 1    1 1 1 1 1 1
n = 2    1 1 2 2 3 3
n = 5    1 1 2 2 3 4

0열은 자기 자신의 money만을 사용할 때를 위해 1로 설정한 것이다.

 

참고 사이트 : https://tosuccess.tistory.com/57