[PROGRAMMERS] 거스름돈 - DP

#include <iostream> #include <vector> #include <algorithm> using namespace std; int change(int total, vector<int> coin) { vector<int>count(total + 1, 0); int coin_count = coin.size(); sort(coin.begin(), coin.end()); for (int j = 0; j < coin_count; j++) { count[coin[j]]++; for (int k = 1; coin[j] + k <= total; k++) count[coin[j] + k] += count[k]; } return count[total]; } //예외가 있음 int main() { int total = 5; vector<int > test{ 1,2,5 }; // 아래는 테스트로 출력해 보기 위한 코드입니다. cout << change(total, test); }