d[i][k] = i번째 동전을 이용해 k원을 만드는 동전의 수 라고 정의하면


리턴값은 다음의 세가지 중 가장 작은 경우가 된다.


1. 현재 동전을 선택하고 다음 동전의 경우를 본다 (1 + d[i+1][k-coins[i]])


현재 동전을 선택했으니까 쓴 동전이 하나 늘어남. 만들어야할 잔액이 k-coins[i]로 줄어들음. 


2. 현재 동전을 선택하고 다음 동전으로 넘어가지 않는다.  


문제에서 같은 동전을 여러번 사용할 수 있다고 했으므로 가능. 마찬가지로 잔액이 줄어들고 사용한 동전이 늘어남. 1 + d[i][k-coins[i]]


3. 현재 동전을 선택하지 않고 다음 동전의 경우를 본다 


잔액이 줄어들지 않고 동전도 사용 안 함. d[i+1][k]



그런데 문제는 k원을 만드는 것이 불가능한 조합도 주어짐.


세가지 케이스가 모두 -1을 리턴했을 경우에는 그 조합으론 k원을 못 만드는거니까 -1을 리턴해야 함. 


소스 코드

#include <cstdio>
#include <vector>
#include <limits.h>
#include <algorithm>
using namespace std;
vector<int> coins;
int cache[101][10001];
const int dp(const int i, const int k){
if(i >= coins.size() || k < 0){
return -1;
}
if(k == coins[i]){
return 1;
}
int &ret = cache[i][k];
if(ret != -100){
return ret;
}
int ans = INT_MAX;
const int solve[3] = {dp(i, k-coins[i]), dp(i+1, k), dp(i+1, k-coins[i])};
for(int i=0; i<3; i++){
if(solve[i] != -1){
ans = min(ans, solve[i]);
}
}
if(ans == INT_MAX){
return ret = -1;
}
else if(ans == solve[1]){
return ret = ans;
}
else{
return ret = ans+1;
}
}
int main(){
int n = 0, k = 0;
scanf("%d %d", &n, &k);
for(int i=0; i<n; i++){
int temp = 0;
scanf("%d", &temp);
coins.push_back(temp);
}
fill(&cache[0][0], &cache[100][10001], -100);
printf("%d", dp(0, k));
return 0;
}