[프로그래머스] 거스름돈 (java)

문제 출처
프로그래머스 - 거스름돈

처음에는 중복조합으로 문제를 풀어나갔지만 효율성에서 걸리게 되었다. 그래서 동적계획법을 의심을 했지만 DP에는 많이 약해서 점화식이 만들지 못해서 다른 블로그들의 정답을 보고 이해를 한다음 글을 작성한다.

1. 사용화폐와 금액대로 만들 수 있는 경우의 수를 표로 만든다.
2. 표를 보고 일정 규칙대로 움직이는 식을 찾는다.

해당 규칙의 식은 기존 거슬러줄 방법 + 추가된 화폐를 사용하여 거슬러줄 방법을 더하는 방식인 것을 확인해볼 수 있다.

import java.util.*;

class Solution {
    public int solution(int n, int[] money) {
        int answer = 0;
        //money종류를 오름차순으로 정렬
        Arrays.sort(money);
        
        int []dp = new int[n+1];
        
        //0원으로 만들 수 있는 방법은 1가지
        dp[0] = 1;
        
        for(int i = 0 ; i < money.length;i++)
        {
            for(int j = money[i]; j <= n; j++)
            {
                //기존 거슬러줄 방법 + 추가된 화폐를 사용하여 거슬러줄 방법
                dp[j] = dp[j] + dp[j - money[i]];
                dp[j] = dp[j] % 1000000007;
            }
        }
        return dp[n];
    }
}

깨달은 점
1. 경우의 수들을 무조건 표를 그려본다.
2. 표를 보면서 점화식을 생각해본다.