프로그래머스 - 거스름돈 [C++]

 이 문제는 다이나믹 프로그래밍을 이용해서 풀었다. 저번에 풀었던 동전 1 문제와 완전히 동일하다. 동전에 대해서 먼저 루프를 돌리면 순서가 보장되므로 순서가 뒤바뀐 채로 경우의 수가 더해지는 일이 없다. 이 때에도 중요한 것은 dp[0] = 1로 초기화해줘야 한다는 것이다.

 

 

 

#include <string>
#include <vector>

using namespace std;

long long dp[100001];

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