[프로그래머스] 12907 거스름돈 - JAVA

[프로그래머스] 12907 거스름돈 - JAVA

문제

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

 

문제 분석

조건

`n`원을 거슬러 줘야 할 때, 보유하고 있는 동전의 종류 `money`를 이용하여 거슬러 줄 수 있는 방법의 가짓수를 구하는 문제이다.

풀이방법

DP를 이용해서 조합의 수를 구하는 문제이다. `dp[i]`는 i원을 만들 수 있는 경우의 수이다. `dp[0] = 1`으로 0원을 거슬러주는 방법은 아무동전도 사용하지 않으므로 1가지 방법이 있다. 코드를 기준으로 예제1번을 순차적으로 진행하면 가진 동전의 종류는 `[1, 2, 5]`이고 목표 금액은 5원이다.

1. 1원짜리로 만들 수 있는 경우의 수

dp = [1, 1, 1, 1, 1, 1]

2. 2원짜리로 만들 수 있는 경우의 수

dp = [1, 1, 2, 2, 3, 3]

2원짜리 동전으로 5원을 만드는 새로운 경우의 수를 구한다고 해보자. 이는 이미 계산된 3원을 만드는 경우의 수(dp[3])에 2원짜리 동전을 하나 추가하는 것과 같다. 따라서 dp[5]에 dp[3]의 값을 더해주는 것이다.

 

코드

class Solution {
    public int solution(int n, int[] money) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int coin : money) {
            for (int i = coin; i <= n; i++) {
                dp[i] = (dp[i] + dp[i - coin]) % 1000000007;
            }
        }
        return dp[n];
    }
}