[DP 응용] BJ_1398, 동전 문제

<문제의 접근>

 이 문제를 Greedy하게만 풀수 있을까? 즉 큰수로 나누어 지면 계속 빼면서 숫자를 구하면 해답일까? 직관적으로 알기 어렵다면 반례를 생각해 보면 된다. 예는 31이 되겠다. 31은 Greedy하게 풀면 25, 1, 1, 1, 1, 1, 1 로 구성되어 총 6개지만, 10, 10, 10, 1로 구성하면 4개로 구성할 수 있다. 따라서 Greedy하게만은 안된다. 그렇다면 DP로만 풀수 있을까? 값의 범위가 $10^{15}$ 로 매우 크기 때문에 배열을 이용해서 단순하게 확장하는 방법으로는 해법에 다가가기 어렵다. 그럼 어떻게 해야한다? 규칙성을 발견해야 한다. 규칙성을 바탕으로 문제를 단순하게 만들 수 있어야 한다. 아래의 글이 도움이 될것 같다.

<코드>

 생각보다 간단하게 작성할 수 있는데, 1부터 100까지는 dp로 풀어낼 수 있어야 한다. 아래와 같이 loop를 돌면서 최소값을 갱신해 준다. 나는 1부터 100까지가 아닌 25까지만 구하고 100까지를 유추하려고 하다가 계속 틀렸습니다를 만났다. 생각보다 단순하지 않으니 잘 보는 것이 좋다. 

void dp_init() {
    dp[1] = 1;
    for (int i=2; i<100;i++) {
        dp[i] = dp[i-1] + 1;
        if (i>=10) dp[i] = min(dp[i], dp[i-10]+1);
        if (i>=25) dp[i] = min(dp[i], dp[i-25]+1);
    }
}

 큰 수부터 작은 수로 진행하면서 코드를 구성하게 되면 생각보다 복잡해 지게 된다. 아래의 코드가 그렇한 예시를 보여준다. 작동은 하지만 생각보다 코드가 복잡해 진다. 

ll solve(ll choco) {
    ll ans = 0;
    if (choco >= arr[15]) return 1;
    if (choco >= arr[14]) {
        ans += (choco / arr[14]);
        choco = choco % arr[14];
    }
    for (int i=12; i>=0;i=i-2) {
        if (choco/arr[i]) {
            int temp = choco/arr[i];
            ans += dp[temp];
            choco = choco % arr[i];
        }
    }
    return ans;
}

 작은 수부터 진행하면 아래와 같이 간단한 수식으로 구성할 수 있다. 정말 간결하면서도 필요한 기능이 담겨져 있다. 이렇게 코드를 구성하면 잔 실수가 없다. 

int solve(ll choco) {
    int ans = 0;
    while (choco) {
        ans += dp[choco%100];
        choco /= 100;
    }
    return ans;
}

 전체 코드를 첨부해 본다. 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;
#define fastio cin.tie(0)->sync_with_stdio(0)

using ll = long long;
using matrix = vector<vector<ll>>;

// 특징적으로 1, 25, 100으로 반복되기 때문에 자릿수를 나누어서 구해줘 본다. 
vector<int> dp(100, 0); // 꼭 100까지는 dp로 풀어야 한다. 25까지 구하면 틀림

void dp_init() {
    dp[1] = 1;
    for (int i=2; i<100;i++) {
        dp[i] = dp[i-1] + 1;
        if (i>=10) dp[i] = min(dp[i], dp[i-10]+1);
        if (i>=25) dp[i] = min(dp[i], dp[i-25]+1);
    }
}
// 어려운 풀이
ll solve(ll choco) {
    ll ans = 0;
    if (choco >= arr[15]) return 1;
    if (choco >= arr[14]) {
        ans += (choco / arr[14]);
        choco = choco % arr[14];
    }
    for (int i=12; i>=0;i=i-2) {
        if (choco/arr[i]) {
            int temp = choco/arr[i];
            ans += dp[temp];
            choco = choco % arr[i];
        }

    }
    return ans;
}

// 쉬운 풀이 
int solve(ll choco) {
    int ans = 0;
    while (choco) {
        ans += dp[choco%100];
        choco /= 100;
    }
    return ans;
}



int main() {
    fastio;
    int t;
    cin >> t;

    dp_init();
    for (int i=0; i<t; i++) {
        ll choco;
        cin >> choco;
        cout << solve(choco) << '\n';
    }
    return 0;
}

 다같이 화이팅 해보자~!