프로그래머스 Lv.3) 거스름돈

거스름돈

코딩테스트 연습 - 거스름돈

풀이

정말정말정말정말 어려운 문제라고 생각한다 주관적으로. n이 100,000 화폐가 100이나 되는 문제기 때문에 dfs로는 풀 수 없다. 가능한 방법이 있다면 알고싶다.. 내가 알고있는 선에서는 풀 수 없었다. 그래서 DP로 풀어야한다는 생각이 들었는데 점화식이 감이 잡히지 않았다.

정말 오랫동안 생각하고 수식을 짜보려 해도 보이지 않았다. 그래서 다른 분의 해설을 보기로 했다.

거스름돈이 0원인 경우 경우의 수가 1이라는데, 문제 조건에서는 100,000 이하의 자연수라는데 0이 자연수에 포함된다니... 구글링을 해보니까 요즘 추세에서는 수학적으로 0이 자연수에 속한다고 한다. 초중고 과정에서 배운 것이 너무 오래됐나보다... 

각설하고, dp 변수는 거스름돈 n을 모두 체크할 수 있는 크기인 n+1로 선언해준다.

그리고 dp[0] =1 (거스름돈 0일 때, 1가지 경우의 수)를 저장해준다.

이후 돈 종류가 담겨있는 money 배열을 돌면서 거스름돈을 주는 경우의 수를 최신화 시켜준다.

이 때, 총 거스름돈에서 이번에 추가하는 돈인 money[i]를 뺀 경우의 수를 추가해주는 것이다.

문제에서 제시한 예시로 예를 들면, for문을 돌면서 j=4, i =1인 경우에 money[1] =2 (돈의 종류)가 된다. 거스름돈 4원을 만들 수 있는 경우의 수에 4 - 2(money[1]) 현재 추가하고있는 money의 종류를 뺀 인덱스의 경우의 수 만큼 더해줘야 한다는 것이다.

이렇게 for문을 돌며 경우의 수를 계속 누적시켜주는 풀이이다.

세상은 넓고 똑똑한 사람은 정말 많구나..

 

로직

1. 거스름돈 n보다 1큼 n+1 크기의 1차원 dp 배열을 선언한다

2. 거스름돈이 0원인 경우, 1가지 경우의 수가 존재하기 때문에, dp[0]에는 1을 저장해 준다. 이후 거스름돈에 딱 맞는 최소 단위가 나올 때 dp에 저장되기도 함.

3. 돈 종류가 담겨있는 money 배열을 순차적으로 탐색한다.

4. 특정 money Index에 대해 해당 인덱스에 담겨있는 돈의 크기 (ex. 2, 4, 10 등등) 부터 거스름돈 총 액인 n까지 1씩 증가하면서 dp값을 최신화 해준다.

5. 해당 화폐를 하나를 뺀 금액을 만들 수 있는 경우의 수를 더해준다.

 

코드

class Solution {
    int MOD = 1000000007;
    public int solution(int n, int[] money) {
        int[] dp = new int[n+1];
        dp[0] =1;
        
        for(int i=0; i<money.length; i++) { // 돈 종류 idx
            for(int j=money[i]; j<=n; j++) { // 돈 종류 ~ 거슬러 줘야하는 금액 N
                dp[j] += dp[j-money[i]];    // 
            }
        }
        return dp[n]%MOD;
    }
}