백준 2294번 동전 2 ( C++ )

문제

https://www.acmicpc.net/problem/2294

 

해설

100 * 10000을 해도 100만밖에 되지 않기 때문에 그냥 풀기

 

코드

#include<iostream>
#include<algorithm>
#include<cstring>
 
using namespace std;
 
const int INF = 87654321;
int n,k,cost[104],ret[10004],tmp;
 
int main(){
  cin >> n >> k;
  fill(ret,ret+10004,INF);
 
  int cnt=0;
  for(int i=0;i<n;i++){
    cin >> tmp;
    if(tmp<=10000){
      cost[cnt] = tmp;
      cnt++;
      ret[tmp] = 1;
    }
  }
 
 
  for(int i=1;i<=k;i++){
    for(int j=0;j<cnt;j++){
      if(i-cost[j]>0) ret[i] = min(ret[i],ret[i-cost[j]]+1);
    }
  }
 
  if(ret[k] >= INF){
    cout << -1;
    return 0;
  }
 
  cout << ret[k];
  return 0;
}