Programmers - 거스름돈 with JAVA (V)

 

 

해설

전형적인 DP를 활용하는 문제이며, 밑에 예시를 통해 설명해보려고 한다.

동전 종류 : [1, 2, 5], 만드려는 수 : 5

 

1. 1원을 사용하는 경우 추가

1원 : [1], 

2원 : [1, 1]

3원 : [1, 1, 1]

4원 : [1, 1, 1, 1]

5원 : [1, 1, 1, 1, 1]

 

2. 2원을 사용하는 경우 추가

1원 : [1]

2원 : [1, 1], [2]

3원 : [1, 1, 1], [1, 2] 

4원 : [1, 1, 1, 1], [1, 1, 2], [2, 2]

5원 : [1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2]

 

주목할 것은 이 부분이다. 

3원 = 기존 3원의 경우의 수 + 1(3-2)원의 경우의 수

4원 = 기존 4원의 경우의 수 + 2(4-2)원의 경우의 수

5원 = 기존 5원의 경우의 수 + 3(5-2)원의 경우의 수

 

생각해보면 예를 들어, 5원은 3원이 갖는 경우의 수들에 2원만 붙여주면 만들 수 있기 때문에 가능하다.

좀 더 설명하자면, 4원을 만들 때, 2원을 사용하여 나머지 2원을 만들어주는 경우의 수를 구하면 된다고 생각하면 된다.

 

 

3. 5원을 사용하는 경우 추가

1원 : [1]

2원 : [1, 1], [2]

3원 : [1, 1, 1], [1, 2]

4원 : [1, 1, 1, 1], [1, 1, 2], [2, 2]

5원 : [1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2], [5]

 

 

아이디어 : DP - 돈의 종류를 순서대로 추가했을 때 만들 수 있는 경우의 수를 구한다.

(1, 2, 5 -> 1원 추가, 2원 추가, 3원 추가)

 

 

코드

class Solution {
    public int solution(int n, int[] money) {
        int[] dp = new int[n+1];
        for(int m : money){
            dp[m] += 1;
            for(int make=m; make<=n; make++){
                dp[make] += dp[make-m];
                dp[make] %= 1000000007;
            }
        }
        return dp[n];
    }
}

 

class Solution {
    public int solution(int n, int[] money) {
        int[] dp = new int[n+1];
        for(int m : money){
            dp[m] += 1;
            for(int i=m; i<=n; i++){
                dp[i] += dp[i-m] % 1000000007;
            }
        }
        return dp[n];
    }
}