[Programmers]LV.3 거스름돈

---

📝 풀이

첫번째로 생각한 것은 DFS로 풀이였습니다. 

import java.util.*;

class Solution {
    static HashSet<String> hs; 
    public int solution(int n, int[] money) {
        hs = new HashSet<>();
        Arrays.sort(money);
        dfs(n, money, new int[money.length], 0);
        return hs.size();
    }

    public static void dfs(int n, int[] money, int[] count, int start) {
        if (n == 0) {
            hs.add(Arrays.toString(count));
            return;
        }
        if (n < 0) return;

        for (int i = start; i < money.length; i++) {
            count[i]++;
            dfs(n - money[i], money, count, i);
            count[i]--;
        }
    }
}
//해쉬셋을 사용한 DFS

해쉬셋을 사용해서 모든 경우의 수를 구하는 방식인데

 

효율성 실패로 다시 작성하였습니다.

 

 

해당 문제의 원리

해당 문제는 사실 DP 문제입니다. 

 

 

DP 방식으로 점화식을 세워봅시다. 일단 0원일 경우는 모든 동전을 쓰지않는 경우의 수 1개가 있습니다. 

 

다음으로 [1,2,5]원을 기준으로 풀어보겠습니다.

 

1원

0	1	2	3	4	5
1	0 + 1 = 1	0 + 1 = 1	0 + 1 = 1	0 + 1 = 1	0 + 1 = 1

 

1원은 모든 수에서 경우의 수를 1개씩 늘립니다.

 

2원

0	1	2	3	4	5
1	1	1 + 1 = 2	1 + 1 = 2	1 + 2 = 3	1 + 2 = 3

 

2원은 2원짜리 1개와 1원 2개로 가능합니다.

 

3원은 기존 경우의 수에 1원짜리를 만드는 경우의 수(1)을 더한 값입니다.

 

4원은 기존 경우의 수에 2원짜리를 만드는 경우의 수(2)을 더한 값입니다.

 

5원은 기존 경우의 수에 3원짜리를 만드는 경우의 수(2)을 더한 값입니다.

 

5원

0	1	2	3	4	5
1	1	2	2	3	3 + 1 = 4

 

5원은 5원짜리 자체인 경우의 수이기에 5원 경우의 수 + 1입니다.

 

 

즉 점화식을 세워보자면

 

DP[i] = DP[i] + DP[i - coin] 입니다. 

 

 

import java.util.*;

class Solution {
    public int solution(int n, int[] money) {
        int dp[] = new int[n + 1];
        dp[0] = 1; 

        for (int coin : money) {
            for (int i = coin; i <= n; i++) { 
                dp[i] += dp[i - coin];
            }
        }
        
        return dp[n];
    }
}