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

프로그래머스 거스름돈

문제풀이

다이나믹프로그래밍 문제를 항상 피하기만 했는데 자주 풀어서 익숙해져야겠다. 직접 표를 그려서 규칙성을 찾아보면 2차원 dp로 풀이가 가능함을 알 수 있다.

• money 배열을 오름차순으로 정렬한다. 화폐를 오름차순으로 차례대로 쓸 것이기 때문이다.
• 2차원 dp 테이블을 만든다. 행은 사용한 화폐 수, 열은 금액을 나타낸다. 따라서 dp[i][j]는 i개의 화폐를 사용해서 j 금액을 만들 수 있는 갯수다.
• 예시를 통해서 테이블을 채워나가다보면 다음과 같은 규칙을 발견할 수 있다.
  • 각 행에서 새롭게 추가된 화폐 미만의 j(금액)에 대해서는 위(dp[i - 1][j])의 값을 그대로 가져온다.
  • 각 행에서 새롭게 추가된 화폐와 j(금액)이 같은 경우에는 위(dp[i - 1][j]) + 1을 한다.
  • 각 행에서 새롭게 추가된 화폐 초과의 j(금액)에 대해서는 위(dp[i - 1][j]) + dp[i][j - 새롭게 추가된 화폐]를 한다.

구현코드

import java.util.*;

class Solution {
    
    static final int MOD = 1000000007;
    
    public int solution(int n, int[] money) {
        int[][] dp = new int[money.length + 1][n + 1];
        
        Arrays.sort(money);
        
        dp[0][0] = 1;
        
        for(int r = 1 ; r < dp.length ; ++r){
            for(int c = 0 ; c < dp[0].length ; ++c){
                if(c < money[r - 1]){
                    dp[r][c] = dp[r - 1][c] % MOD;
                } else if(c == money[r - 1]){
                    dp[r][c] = dp[r - 1][c] + 1 % MOD;
                } else {
                    dp[r][c] = dp[r - 1][c] + dp[r][c - money[r - 1]] % MOD;
                }
            }
        }
        
        return dp[money.length][n];
    }
}