boj 1398 동전 문제

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

 

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

위 동전들을 적절히 사용하여 N을 만들기 위한 최소 갯수를 구하는 문제입니다.

 

동전들을 3개씩 끊어본다면

(1, 10, 25)

(1, 10, 25) * 100

(1, 10, 25) * 100 * 100

(1, 10, 25) * 100 * 100 * 100

이런식으로 규칙이 된다는 것을 알 수 있습니다.

그러면 굳이 문제에서 요구하는 큰 범위까지 갈 필요 없이 100 단위로 끊어서 접근한다면 간단하게 해결할 수 있습니다.

 

같은 금액에서의 답은 똑같기 때문에 dp를 사용했습니다.

그리고 dp 배열을 초기화할 필요도 없습니다.

(1, 10, 25) 으로 99원을 만들든, (100, 1000, 2500) 으로 9900원을 만들든 똑같은 결과가 나오기 때문입니다.

여기까지 오셨다면 구현은 간단합니다.

 

 

#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX 101
using namespace std;
typedef long long ll;
 
int dp[MAX];
int list[3] = { 1,10,25 };
ll N;
 
int solve(int n) {
    if (!n) return 0;
 
    int& ret = dp[n];
    if (ret != -1) return ret;
 
    ret = 1e9;
    for (int i = 0; i < 3; i++) {
        if (n < list[i]) continue;
 
        ret = min(ret, solve(n - list[i]) + 1);
    }
    return ret;
}
 
void func() {
    memset(dp, -1, sizeof(dp));
    
    int ret = 0;
    while (N) {
        ret += solve(N % 100LL);
        N /= 100LL;
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
    while (tc--) {
        input();
        func();
    }
 
    return 0;
}