BOJ2294: 동전 2

작성일

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

  • 거의 6달치를 날리고 오랜만에 쓰는 문제풀이
  • 이제 열심이 풀어서 익스를 따야지 -_-
  • 문제 자체는 심플한 무한대 냅색문제
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;


class Solution {
  int N, K;
  vector<int> arr, dp;
public:
  void input() {
    scanf("%d%d", &N, &K);
    arr.resize(N);
    for (int i = 0; i < N; i++)
      scanf("%d", &arr[i]);
    dp.resize(K+1, 0xffff);
    dp[0] = 0;
  }
  int solve() {
    for (int i = 0; i < N; i++)
      for(int j = arr[i]; j <= K; j++)
        dp[j] = min(dp[j], dp[j - arr[i]] + 1);
    return dp[K];
  }
};


int main() {
  Solution sol;
  sol.input();
  int ret = sol.solve();
  cout << (ret == 0xffff ? -1 : ret);
}