재정의 및 추상화

• 거스름돈에 맞춘 금액을 만들기 위해 만들 수 있는 동전들의 가짓수를 구하는 문제이다.

계획 및 검증

• 백트래킹으로 탐색 가면
  • 거의 $O(n^2)$
  • 탐색했던 액수를 다시 탐색하는 작업을 반복해야하니까
• 반복 작업을 없앤다? DP가 필요
• n원을 만든다고 할 때 동전을 0~i번째까지 사용했을 때 만들 수 있는 가짓수를 memo[n][i]라고 정의했다.

풀이

import java.util.*;

class Solution {
    private int[][] memo;
    
    
    public int solution(int n, int[] money) {
        int answer = 0;
        memo = new int[money.length][n+1];
        
        for(int i=0; i<money.length; i++) {
            Arrays.fill(memo[i], -1);
            memo[i][0] = 1;
        }
        Arrays.sort(money);
        memoization(n, money, money.length-1);
        
        return memo[money.length-1][n];
    }
    
    private int memoization(int n, int[] money, int start) {
        if(memo[start][n]!=-1) {
            return memo[start][n];
        }
        
        memo[start][n] = 0;
        for(int i=start; i>=0; i--) {
            if(n<money[i])continue;
            memo[start][n] = (memo[start][n]+memoization(n-money[i],money,i))%1_000_000_007;
        }
        
        return memo[start][n];
    }
}

회고

• 자꾸 똑같은 실수 반복하는데, 브루트포스 백트래킹 기본적인 것부터 시작해야한다.
  • 빨리 해보려다가 더 늦게 풀린다.