[BAEKJOON] 2294 동전 2

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #include <algorithm> #define MAX 99999999 using namespace std; int main() { int n, goal; scanf("%d %d", &n, &goal); vector<int>number(n), DP(100001, MAX); for (int j = 0; j < n; j++) scanf("%d", &number[j]); sort(number.begin(), number.end()); for (int j = 0; j < n; j++) { DP[number[j]] = 1; for (int k = number[j] + 1; k <= goal; k++) DP[k] = min(DP[k], DP[k - number[j]] + 1); } if (DP[goal] == MAX) printf("%d", -1); else printf("%d", DP[goal]); return 0; }