[프로그래머스] Lv.3 거스름돈.java

거스름돈.java

class Solution {
    public int solution(int n, int[] money) {
        int[][] dp = new int[money.length+1][n+1];
        int answer = 0;
        
        for(int i=1; i<money.length+1; i++){
            for(int j=0; j<n+1; j++){
                if(j==0){
                    dp[i][j] = 1;
                }
                else{
                    if(j<money[i-1]){
                        dp[i][j] = dp[i-1][j];
                    }else{
                        dp[i][j] = (dp[i-1][j] + dp[i][j-money[i-1]]) % 1000000007;
                    }
                }
            }
        }
        return dp[money.length][n];
    }
}

동적 계획법(Dynamic Programming)을 이용해 n원을 money 배열에 있는 동전으로 만들 수 있는 경우의 수를 구하는 문제입니다.

dp[i][j]는 i개의 동전으로 j원을 만들 수 있는 경우의 수를 의미합니다. 그렇다면, 첫번째 동전을 추가하여 j원을 만들 수 있는 경우의 수는 첫번째 동전을 사용하지 않은 경우의 수(dp[i-1][j])와 첫번째 동전을 사용한 경우의 수(dp[i]j-money[i-1]])를 더한 값이 됩니다. 첫번째 동전의 가치가 money[i-1]이므로, j-money[i-1]원을 만드는 경우의 수를 더하면 첫번째 동전을 사용한 j원을 만드는 경우의 수가 됩니다. 만약, j원보다 첫번째 동전의 가치가 크다면 첫번째 동전을 사용할 수 없으므로, 첫번째 동전을 사용하지 않은 경우의 수와 같습니다.

그리고, 만약 j원이 0원이라면 0원을 만드는 방법은 한 가지 뿐이므로 dp[i][j] = 1이 됩니다.

그러면 dp 배열을 구한 후, dp[money.length][n]을 반환해주면 n원을 money 배열의 동전으로 만들 수 있는 경우의 수가 됩니다. 이때, 1000000007로 나눈 나머지를 반환해야 하므로, % 1000000007을 해줍니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges