BOJ2294: 동전 2 작성일 2021-02-15 https://www.acmicpc.net/problem/2294 거의 6달치를 날리고 오랜만에 쓰는 문제풀이 이제 열심이 풀어서 익스를 따야지 -_- 문제 자체는 심플한 무한대 냅색문제 123456789101112131415161718192021222324252627282930313233#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); }