baekjoon 2294:동전 2

baekjoon 2294 동전 2

2294번 동전 2

접근

각 동전이 서로 나눠지는 관계가 보장된다면 이 동전 문제는 greedy 문제가 된다.
하지만 그렇지 않은 경우도 있기 때문에 dp로 모든 경우의 수를 직접 해봐야한다.
각 동전을 무제한적으로 쓸 수 있기 때문에 각 동전을 몇개 썼는지 여부는 기록할 필요가 없다.
단지 내가 채워야하는 돈만 dp로 넘겨주면 될 것 같다.

코드

//2294
#include <iostream>
#include <array>
#include <vector>
using namespace std;
array<int, 10001> cache;
int dp(int k, vector<int>& v);
int m;
int main(){
  int n; cin >> n >> m;
  vector<int> size(n, 0);
  for(int i = 0; i < n; i++){
    cin >> size[i];
  }
  fill(cache.begin(), cache.end(), -1);
  cout << dp(m, size);
  
  
  return 0;
}
int dp(int k, vector<int>& v){
  if(k == 0) return 0;
  int& ret = cache[k];
  if(ret != -1) return ret;
  ret = 1e6;
  for(int i = 0; i < v.size(); i++){
    if(v[i] > k) continue;
    ret = min(ret, dp(k - v[i], v) + 1);
  }
  if(ret == 1e6 && k == m) ret = -1;
  return ret;
}

배운 점

기초적인 dp 문제였다.