프로그래머스 - 거스름돈

프로그래머스 - 거스름돈

dp[i][j]가 의미하는 것은 money[i]를 추가했을 때, j원을 나타내는 경우의 수이다.
dp[i][j] = dp[i-1][j] + dp[i]j - money[i]]인데, 이는 즉,

money[i]를 추가하지 않았을 때 j원을 나타내는 경우의 수와 j - money[i]원을 나타내는 경우에서 money[i]만큼을 추가했을 때의 경우의 수의 합이다.

코드는 아래와 같다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int n, vector<int> money) {
    int answer = 0;
    int s = money.size();
    vector<vector<int>> dp(s, vector<int>(n + 1, 0));
    for(int j=0;j<=n;j+=money[0]) 
        dp[0][j] = 1;
    
    for(int i=1;i<s;i++) {
        for(int j=0;j<money[i];j++) 
            dp[i][j] = dp[i - 1][j];
        for(int j=money[i];j<=n;j++) 
            dp[i][j] = (dp[i][j-money[i]] + dp[i - 1][j]) % 1000000007;
    }
    
    answer = dp[money.size() - 1][n];
    
    return answer;
}