/*
boj2294.cpp
2021-01-08
동전 2
*/
#include <bits/stdc++.h>
#define MAX 10'001
using namespace std;
vector<int> money;
vector<int> dp;
int f(int k) {
if (dp[k] != -1) return dp[k];
int cnt = MAX;
if (k < money[0]) return -1;
for (int i = money.size() - 1; i >= 0; i--) {
if (k == money[i]) {
cnt = 1; break;
}
if (k - money[i] >= money[0]) {
cnt = min(cnt, f(k - money[i]) + 1);
}
}
dp[k] = cnt;
return dp[k];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, k; cin >> n >> k;
dp.resize(k + 1, -1);
for (int i = 0; i < n; i++) {
int tmp; cin >> tmp;
money.push_back(tmp);
}
sort(money.begin(), money.end());
int ans = f(k);
if (ans != MAX) //이 조건 없으면 틀림
cout << ans;
else
cout << -1;
}
정확한 알고리즘을 생각해서 푼 게 아니라, 끼워맞추기 식으로 풀었음ㅠ
TopDown방식으로 풀었는데, 이 문제는 BottomUp방식으로 푸는게 더 좋을듯함.
/*
boj2294.cpp
2021-01-08
동전 2
*/
#include <bits/stdc++.h>
#define MAX 10'001
using namespace std;
vector<int> money;
vector<int> dp;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, k; cin >> n >> k;
dp.resize(k + 1, MAX);
dp[0] = 0;
for (int i = 0; i < n; i++) {
int tmp; cin >> tmp;
money.push_back(tmp);
}
sort(money.begin(), money.end());
for (int i = 0; i<n; i++) {
for (int j = money[i]; j <= k; j++) {
dp[j] = min(dp[j - money[i]] + 1, dp[j]);
}
}
if (dp[k] == MAX)
cout << -1;
else
cout << dp[k];
}
https://jaemin8852.tistory.com/163 참고해서 풀었다!
훨씬 간결한 것 같다..!
왜인진 모르겠지만 TopDown방식으로 풀려고 한다..
소스코드를 적기 전에 충분히 아이디어를 생각 하고 풀기!!!!