[프로그래머스/Level 3] 거스름돈 (C++)

programmers.co.kr/learn/courses/30/lessons/12907

코딩테스트 연습 - 거스름돈

DP 유형의 문제

dp[n]의 점화식을 'n원을 만들 수 있는 조합의 수'로 정의합니다. 여기서 조합의 수라고 정의한 이유는 동전을 더하는 순서에 따라 답이 달라질 수 있기 때문입니다. 

 

예를들어 1, 2, 5 종류로 3원을 만들 때, 다음과 같이

1+1+1 = 3

2+1 = 3

1+2 = 3

 

1원과 2원을 사용하는 경우가 중복되어서 나오는 경우가 발생합니다. 따라서 이를 고려하여 조합의 수를 구해야합니다.

(동전의 금액이 낮은 순서로, 1 -> 2 -> 5의 순서로 점화식을 통해 n원을 만들 수 있는 조합의 수를 구하기) 

 

ex)

dp[1] += dp[0] : 1

dp[2] += dp[1] : 1

dp[3] += dp[2] : 1

dp[4] += dp[3] : 1

dp[5] += dp[4] : 1

 

dp[2] += dp[0] : 2

dp[3] += dp[1] : 2

dp[4] += dp[2] : 3

dp[5] += dp[3] : 3

 

dp[5] += dp[0] : 4

 

#include <string>
#include <vector>
using namespace std;

int dp[100001]; // n원을 만들 수 있는 조합의 수

int solution(int n, vector<int> money) {
    dp[0] = 1; // 0원을 만들 수 있는 수 : 1개(아무것도 선택하지 않는다.)
    
    for(auto m : money) {
        for(int i = m; i <= n; i++) {
            dp[i] += dp[i - m] % 1000000007;
        }
    }
    
    return dp[n];
}