[백준 1398] 동전 문제

문제

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

 

알고리즘

DP, Greedy

 

풀이

최소 동전의 수를 묻는 문제입니다.

 

주어진 동전들이 Canonical 하다면 그리디하게 풀 수 있습니다. 이 문제에서는 그렇지 않으므로 DP를 이용해서 풀어야합니다. 일반적으로 주어진 금액의 크기만큼 배열크기를 선언하지만 이 문제에서는 금액의 크기가 $10^{15}$이므로 배열선언도 어렵습니다.

 

1, 10, 25, 100, 1000, 2500, 10000, 100000, ...

 

하지만 동전들을 3개씩 나누어 본다면 배수관계를 만족함을 알 수 있습니다. 

 

(1 10 25), (100 1000 2500), (10000 100000 ...)

 

즉 DP를 100씩 끊어서 사용하면 됩니다.

 

코드

#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;

#define int long long

int T, v, ans;
int cache[105];
int coin[3] = {1, 10, 25};
signed 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 >> T;
    memset(cache, 0x3f, sizeof(cache));
    cache[0] = 0;
    for (int i = 1; i < 100; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (i - coin[j] >= 0)
                cache[i] = min(cache[i - coin[j]] + 1, cache[i]);
        }
    }
    while (T--) {
        ans = 0;
        cin >> v;
        while (v) {
            ans += cache[v % 100];
            v /= 100;
        }
        cout << ans << '\n';
    }
    return 0;
}