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

n원의 거스름돈을 주는 경우의 수를 푸는 문제이다.

우선 0원일 때에 경우의 수 1을 입력한다. 그 후 금액별로 n원 까지 경우의 수를 구하는데

구하려는 금액에 거스름돈의 단위를 뺀 값의 dp값을 더해주면 된다.

#include <string>
#include <vector>

using namespace std;

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