BOJ 백준 1398 : 동전 문제

시작하면서

　이번 문제는 그리디 알고리즘(Greedy Algorithm)과 동적 계획법(Dynamic Programming)이 살짝 섞인 문제이다.

BOJ 1398 - 동전 문제

​

문제 이해

​ 이 문제는 그리디 알고리즘과 동적 계획법을 적절히 섞어서 사용해야 한다. 문제의 핵심은 다음 2가지이다.

• 동전은 10^k와 25*100^k 로 종류가 제한되어 있다.
• 1, 10, 25 / 100, 1000, 2500 / … : 100 단위로 끊어진 규칙성이 있다.

​ 위 두 규칙을 생각하면 차의 가격이 얼마가 되었든 100단위, 즉 2자리로 끊어서 계산하면 된다. 이를 계산할 때에는 1~99까지의 최소 코인을 미리 계산해서 저장해둔 후에 가져오면 더 효율적으로 계산할 수 있다.

1. 1~99 가격의 최소 코인을 DP벡터에 구해서 저장한다.
2. 차량 가격을 맨 앞부터 2자리씩 끊어서 필요한 코인 개수를 구한다.
   • 홀수라면 맨 앞자리를 하나 늘려서 2자리로 만들어서 계산 : 1 -> 01, 5 -> 05
3. 끝 자리까지 계산해서 답을 구한다.

​

해결

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

vector<int> GetDpVector()
{
    vector<int> dp;

    for (int i = 1; i <= 99; i++)
    {
        int numberOfTwentyFive = 0;
        int minimum = 99999999;

        numberOfTwentyFive = (i / 25);

        while (numberOfTwentyFive >= 0)
        {
            int value = 0, minimumCopy = 0;
            
            value = i;

            // 1. 25로 나누는 수
            minimumCopy = numberOfTwentyFive;
            value -= 25 * numberOfTwentyFive;

            // 2. 10으로 나누는 수
            minimumCopy += (value / 10);
            value %= 10;

            // 3. 1로 나누는 수
            minimumCopy += value;

            // 4. get minimum
            minimum = min(minimum, minimumCopy);

            numberOfTwentyFive--;
        }

        dp.push_back(minimum);
    }

    return dp;
}

int GetNumberDigit(long long number)
{
    int digit = 0;

    while (number > 0)
    {
        digit++;
        number /= 10;
    }

    return digit;
}

int GetMinimumNumberOfCoinsRequired(const vector<int>& dp, long long carPrice)
{
    int coinCount = 0;
    int digit = GetNumberDigit(carPrice);

    // 두 자리로 끊기 위해, 홀수면 자리수를 1개 늘려서 맨 앞에 0을 붙여준다.
    if (digit % 2 != 0)
    {
        digit++;
    }

    while (carPrice > 0)
    {
        int firstTwoDigits = carPrice / pow(10, digit - 2);

        coinCount += dp[firstTwoDigits - 1];
        carPrice -= firstTwoDigits * pow(10, digit - 2);
        digit -= 2;
    }

    return coinCount;
}

int main()
{
    // sync off
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // sync off
    
    int T;
    long long carPrice;
    
    cin >> T;

    vector<int> dp = GetDpVector();
    for (int i = 0; i < T; i++)
    {
        cin >> carPrice;
        cout << GetMinimumNumberOfCoinsRequired(dp, carPrice) << "\n";
    }

    return 0;
}