[알고리즘/C++] 최소 지폐 개수 구하기(동적 프로그래밍)

각 가치가 A, B, C, D인 화폐가 있다고 하자. 최소한의 화폐 장수를 사용하여 특정 액수 X를 만들어야 하는 문제이다. 최적해의 해를 빠르게 구하기 위해서는 동적 프로그래밍(Dynamic Programming)을 이용하여야 한다. typedef vector vi; #define inf pow(2,30); int minNumCoin(int curBalance, vi coinCase, map& selected) { if (curBalance < 0) { return inf; } else if (curBalance == 0) { return 0; } else { int ans = inf; for (auto coin : coinCase){ int pre_result = minNumCoin(curBalanc..

2023.07.21