[BOJ/백준] 2294 (동전 2) C++

썰·2021년 1월 8일

DP algorithm boj

boj

목록 보기

3/5

주제

dp

boj2294

아이디어

처음에는 TopDown방식으로 풀어나감!

소스코드

소스코드1 (TopDown)

/*
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방식으로 푸는게 더 좋을듯함.

소스코드2 (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];
}