[BAE/<JOON> 문제풀이] 2091. 동전

https://www.acmicpc.net/problem/2091

2091번: 동전

서론

평범한 동전문제. DP 로 풀었다. 동전이 모두 배수 관계지만 특정 동전의 개수가 0일 경우 배수 관계가 성립하지 않을 수 있어 그리디 풀이는 배제했다. ( 10, 25 동전만 있는 경우 )

---

풀이

점화식

• DP[i][j] = i 번째 동전까지만 사용해 j원을 만들 때 최대 동전 사용 횟수와 각 동전을 쓴 횟수 ( [1~4]까지 동전, [0]은 총 횟수 )
• DP[i][j] = max(DP[i - 1][[j - 현재 동전 가치][0] + 1, DP[i - 1][j])

또한 동전마다 제한이 있으므로 현재 사용하는 동전을 이미 전 단계인 DP[i - 1][j] 에서 모두 쓴 경우를 검사해 제외해야 한다.

---

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using ll = long long;
int mvx[6] = { 0, 1, 1, -1, -1, 0 };
int mvy[6] = { 1, 1, 0, 0, -1, -1 };
struct node {
    vector<int> arr;
    int cnt = 0;
};
struct cmp {
    bool operator() (node a, node b) {
       return a.cnt > b.cnt;
    }
};
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int x, a, b, c, d; cin >> x >> a >> b >> c >> d;
    vector<int> cv = { -1, 1, 5, 10, 25 };    
    vector<int> cc = { -1, a, b, c, d };
    vector<vector<vector<int>>> dp(5, vector<vector<int>>(x + 1, vector<int>(5)));
    for (int i = 1; i <= 4; i++) {
        for (int j = 0; j <= x; j++) {
            dp[i][j] = dp[i - 1][j];
        }
        for (int j = cv[i]; j <= x; j++) {
            int s1 = dp[i][j - cv[i]][0] + 1;
            if (j - cv[i] > 0 && dp[i][j - cv[i]][0] == 0) continue;
            if (dp[i][j][0] < s1 && dp[i][j - cv[i]][i] < cc[i]) {
                dp[i][j] = dp[i][j - cv[i]];
                dp[i][j][i]++; dp[i][j][0]++;
            }
        }       
    }
    for (int i = 1; i <= 4; i++) {
        cout << dp[4][x][i] << " ";
    }
    return 0;
}