[Programmers] Lv3 거스름돈

Programmers Lv3 거스름돈

문제링크

대표적인 Knapsack 문제로 동적 계획법을 이용하여 풀 수 있는 문제이다.

풀이 과정

1. 1차원 배열 int dp[n+1] 을 선언한다. dp[i] 는 i원을 거슬러 줄 수 있는 경우의 수를 나타낸다.
2. dp[i] = 1 if i % money[i] == 0 else 0 for i in range(0, n+1) 로 초기화를 수행한다.
3. 거슬러 줄 금액 remain과 화폐단위 money[i] 대하여 remain - money[i] 는 다음과 같은 점화식을 갖는다
dp[remain] += dp[remain - money[i]];
4. 즉 어떤 금액 remain을 거슬러 주는 경우의 수는 remain - money[i] 만큼의 금액을 거슬러 주는 경우의 수들을 더한 것과 같다.

위 과정을 코드로 옮겨보자

import java.util.*;

class Solution {
    static int MOD = 1000000007;

    public int solution(int n, int[] money) {
        int answer = 0;
        int[] dp = new int[n+1]; //dp[n] 은 n원을 거슬러주는 방법의 수
        dp[0] = 1;
        Arrays.setAll(dp, p->p % money[0] == 0 ? 1 : 0);

        for(int i = 1 ; i < money.length ; i++) {
            int target = money[i];

            for(int j = target ; j <= n ; j++) {
                dp[j] += dp[j - target] % MOD; // 문제 조건에 1000000007 로 나눈 나머지를 요구했기 때문에 모듈러 연산 추가
            }
        }

        answer = dp[n];

        return answer;
    }
}