[boj 1398] 동전문제

www.acmicpc.net/problem/1398

 

tag : 그리디,디피

설명 : 동전 문제를 풀 때, 그리디로 해결하는 경우, 또 DP로 해결하는 경우 2가지가 있었다.

그리디로 풀 수 있는 조건은 무조건 큰 단위 동전을 많이 쓰는 것이 가장 이득인 경우 이며, 이를 만족하려면 각 동전들이 서로 배수 관계를 이루어야 한다.( ex 1원 10원 100원..)

문제에서 먼저 같은 규칙을 갖는 작은 단위부터 생각을 해보자.

1,10, 25원 동전이있을때, 25원 동전을 쓸 수 있다고 무조건 쓰는 것이 가장 이득이 아님을 알 수 있다.

이는 25원이 10원의 배수가 아니여서 이기도 하지만,

가장 간단한 예시로 40원을 25원을 쓴 경우 (25*1 + 10 *1 + 1*5 ) 이렇게 총 7개가 필요하지만

25원을 쓰지 않은경우 (10*4) 4개의 동전만으로 만들 수 있다.

따라서 DP로 이부분을 해결해야한다.

또 가지고 있는 동전들의 관계를 보면

(1, 10, 25 ) , (100,1000,2500), (10000,100000,250000)..... 이렇게 3개씩 각각 100배차이로나는 묶음으로 만들 수가 있는데 각각의 묶음은 다른 묶음의 배수이므로, 무조건 큰 묶음 먼저 쓰는 것이 이득임을 알 수 있다.

dp[100] : 1 10 25원으로 i원을 만드는 최소 동전의 개수

로 배열을 만들고,

100씩나눠가면서 처리하면 된다!

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 2e9;
typedef pair<int,int> pi;
int dp[101];// 1 10 25..로 i원을 만드는 최소한의 개수
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    fill(dp,dp+101,MAX);
    dp[0]=0;
    vector<int> v = {1,10,25};
    for(int i =1; i <= 99; i++){
        for(int x : v){
            if(i-x>=0)dp[i]=min(dp[i],dp[i-x]+1);
        }
    }
    while(t--){
        ll n;
        cin >> n;
        ll ans= 0;
        while(n){
            ans += dp[n%100];
            n/=100;
        }
        cout << ans<<"\n";
    }
}