BOJ 2294번 동전 2

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

github : https://github.com/junho0956/Algorithm/blob/master/2294/2294/%EC%86%8C%EC%8A%A4.cpp

 

동전2 문제의 경우 2차원 dp로 해결할 수 있습니다.

지금까지 합쳐진 돈의 액수를 total로 보고 재귀로 구현해주시면 쉽게 해결할 수 있습니다.

 

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
 
int dp[101][10001];
int N, won;
int arr[101];
 
int dfs(int nth, int total) {
    if (nth > N || total > won) return 1000;
    if (total == won) 
        return 0;
    
    int& res = dp[nth][total];
    if (res != -1)return res;
 
    res = 1000;
    for (int i = nth; i <= N; i++) {
        res = min(res, dfs(i, total + arr[i]) + 1);
    }
 
    return res;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> won;
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i <= N; i++) cin >> arr[i];
 
    int ans = dfs(1, 0);
    if (ans == 1000) cout << "-1";
    else cout << ans;
 
    return 0;
}