거스름돈

문제

https://programmers.co.kr/learn/courses/30/lessons/12907

코드

import java.util.*;
class Solution {
    // static int answer = 0;
    // int dp[][] = new int[100001][100];
//     void dfs(int[] money, int left, int threshold){
//         if(left == 0){
//             answer = (answer+1)%1000000007;
//             return;
//         }else{
//             if(threshold < money.length && left >= money[threshold])
//                 dfs(money, left-money[threshold], threshold);
//             if(threshold+1 < money.length)
//                 dfs(money, left, threshold+1);
//         }
//     }
//     int mem(int[] money, int left, int threshold){
//         if(left == 0)
//             return dp[left][threshold] = 1;
//         else if(dp[left][threshold] != -1){
//             return dp[left][threshold];
//         }
//         else{
//             dp[left][threshold] = 0;

//             if(threshold < money.length && left >= money[threshold]){
//                 dp[left][threshold] += mem(money, left-money[threshold], threshold);
//                 dp[left][threshold] %= 1000000007;
//             }
//             if(threshold+1 < money.length){
//                 dp[left][threshold] += mem(money, left, threshold+1);
//                 dp[left][threshold] %= 1000000007;
//             }           
//             return dp[left][threshold];
//         }
//     }

    private int mem(int dp[], int money[], int left, int threshold){
        if(left == 0){
            return dp[left] = 1;
        }
        else if(dp[left] != -1)
            return dp[left];
        else{
            dp[left] = 0;
            if(threshold < money.length && left >= money[threshold]){
                dp[left] += mem(dp, money, left-money[threshold], threshold);
                dp[left] %= 1000000007;
            }
            if(threshold+1 < money.length){
                dp[left] += mem(dp, money, left, threshold+1);
                dp[left] %= 1000000007;
            }           
            return dp[left];        
        }
    }


    public int solution(int n, int[] money) {
        int answer = 0;
        // answer = mem(money, n, 0);
        // // dfs(money, n, 0);
        // int dp[] = new int[n+1];
        // for(int i=0; i<dp.length; i++)
        //     dp[i] = -1;
        // answer = mem(dp, money, n, 0);

        for(int i=0; i<=n; i++)
            if(i%money[0] == 0)
                dp[i] = 1;

        for(int i=1; i<money.length; i++){
            for(int j=money[i]; j<=n; j++)
                dp[j] += dp[j-money[i]];
        }

        answer = (int)(dp[n]%1000000007);


        return answer;
    }
}

피드백

• 메모이제이션으로 까지 시도했으나 실패
  • dp[left][threshold]의 식으로 했는데, 이것은 생각해보면 O(N^3)의 복잡도를 일으키게 된다. 당연이 TLE가 날 것이다.
  • 그러면 dp의 한 차원을 줄여볼 수 있을까? 라는 생각이 드는데... threshold는 없애도 된다.
• 일단 해답은 간단하다.
  • 0번째 돈으로 bottom을 초기화 하고 하나씩 올리면서 이전 iteration 에서 된 거에 더하는 식이다.
• 내 식은 왜 틀렸을까?
  • 1. 단순 dfs
    • O(N^3)이다.
  • 2. dp[][]
    • O(N^3)이다.
  • 3. 내가 만든 dp[]
    • 이러면 O(N^2) 아냐? 라고 생각했지만 결론은 아니고, 오히려 잘못된 값을 가진다.
    • 이런경우가 있을 수 있다.
      • {1,1,1,1,1} 방문
      • {1,2,1,1} 이 방문된다.
      • 이 경우, 오히려 money 순서가 깨져서 1번 코드보다 방문을 더 많이 할 수 있다.