[2158] 동전 교환

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

처음에 그리디로 접근했는데.. 생각해보니 잘못된 접근이었습니다.

1, 10, 25, 100, 1000, 2500, ... 이렇게 코인이 진행되는데

이 수들이 서로 배수라면 그리디로 해결해도 괜찮지만

10에서 25, 1000에서 2500 ...... 이런식으로 배수가 아닌 경우가 존재합니다.

그렇기 떄문에 그리디는 잘못된 방법입니다.

다음에 생각한 방법이 재귀를 이용하여 완전탐색으로 해봤습니다.

결과는 잘나오나 어떤 부분이 틀린지 잘모르겠습니다.

그래서 블로그를 찾다 보니 푸는 방법이 굉장히 신기했습니다.

1, 10, 25

100, 1000, 2500

10000, 100000, 250000

.

.

.

한단계 단계가 100으로 나눌 떄 같아지는 것을 이용한 풀이입니다.

dp를 이용해서

0~99까지 최소 코인 수를 구합니다.

그 후에 입력 받은 n을 100씩 나누면서 더해주면 답이 되는 문제입니다..

어떻게 생각하지 ..ㅡ.ㅡ..... 천재들...

아래는 풀 코드입니다.

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
#include <string>
 
#define ll long long
#define INF 0x7fffffff
#define MOD 1000000
#define MAX_SIZE 101
#define mp make_pair
#define pii pair<int, int>
using namespace std;
 
int main() {
    int coin[] = { 1, 10, 25 };
    int dp[100] = { 0, };
 
    for (int i = 1; i < 100; i++) {
        dp[i] = INF;
        for (int j = 0; j < 3; j++) {
            if (i - coin[j] >= 0) {
                dp[i] = min(dp[i], dp[i - coin[j]] + 1);
            }
        }
    }
 
    int t;
    cin >> t;
 
    while (t--) {
        ll n;
        cin >> n;
 
        ll ret = 0;
 
        while (n) {
            int nMod100 = n % 100;
 
            ret += dp[nMod100];
            n /= 100;
        }
 
        cout << ret << '\n';
    }
 
    return 0;
}