(프로그래머스 c++)거스름돈

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

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

 

DP 사용.

백준 2293 동전1 문제와 같다.

eunchanee.tistory.com/296

(백준 c++)2293 동전 1

#include <string>
#include <vector>
#include <iostream>

using namespace std;

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