[백준 2091] 동전

문제

www.acmicpc.net/problem/2091

 

알고리즘

DP

 

풀이

만들 값과 동전의 갯수가 주어졌을 때, 동전을 최대로 사용하여 해당 값을 만드는 문제입니다.

 

최소동전을 사용하는 것은 동전들의 관계가 canonical 하므로 그리디로 해결가능하나 최대로 사용하기 위해선 다이나믹 프로그래밍을 이용해야합니다.

 

$cache[i]$= i원을 만들 때, 사용하는 최대 동전의 갯수 

 

작은 동전부터 작은 값의 테이블을 채워나가면 됩니다. 특정 값까지 테이블이 채워져 있다면, 당연하게도 동전을 많이 사용하려면 다음 테이블을 갱신할 때 작은 동전부터 사용해야하기 때문입니다. 테이블에 채워져 있는 값을 발견했다면 그 값 이전은 이미 최대로 동전을 사용하기를 마친 상태이고, 값 뒤에만 갱신해나가면 됩니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

int coin[4] = { 1, 5, 10, 25 };

int cache[10001], par[10001], used[26], cnt[4], x;

bool get_max(int& a, int b) {
    a = max(a, b);
    return a == b;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> x;
    rep(i, 4) {
        cin >> cnt[i];
    }
    cache[0] = 1;

    rep(i, 4) {
        for (int j = x; j >= 0; --j) {
            if (cache[j]) {
                for (int k = 1; k <= cnt[i]; ++k) {
                    int nxt = j + coin[i] * k;

                    if (nxt > x)
                        break;
                    if (get_max(cache[nxt], cache[j] + k)) {
                        par[nxt] = nxt - coin[i];
                    } else
                        break;
                }
            }
        }
    }

    if (!cache[x])
        cout << "0 0 0 0";
    else {
        while (x) {
            used[x - par[x]]++;
            x = par[x];
        }
        cout << used[1] << ' ' << used[5] << ' ' << used[10] << ' ' << used[25];
    }

    return 0;
}