[JAVA/DP] 프로그래머스 거스름돈

1. 문제

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

프로그래머스

 

2. 풀이

• DP를 이용해 문제를 풀이한다. 
• DP[N]이 N에 해당하는 거스름돈을 구하는 방법의 갯수를 의미한다면.
  • DP[N]은 DP[N-화폐 종류 1] + DP[N-화폐 종류 2] + DP[N-화폐 종류 3]....이라고 생각할 수 있다,
  • 위 내용을 for문을 사용해 구현하면 아래의 코드와 같다.
  • 이 때, 화폐 하나로만 거스름돈을 채울 수 있는 경우를 포함하기 위해 DP[0] = 1로 초기화한다.

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

 

3. 코드

import java.util.*;

class Solution {
    public int solution(int n, int[] money) {
        int answer = 0;
        Arrays.sort(money);
        
        int[] dp = new int[n+1]; // 인덱스에 해당하는 거스름돈을 만드는 경우의 수
        dp[0] = 1;
        for(int i = 0; i < money.length; i++){
            for(int j = money[i]; j <= n; j++){
                dp[j] += dp[j - money[i]] % 1000000007;
            }
        }

        answer = dp[n];
        return answer;
    }
}