[ BOJ 백준 1398번 - 동전 문제 ] 해설 및 코드

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

 

 

목적

1, 10, 25, 100, 1000, 2500, 10000, 100000, ... 과 같이 0보다 크거나 같은 모든 K에 대해서 10^K인 동전과 25*100^K인 동전들이 있다. 차를 사기위한 동전의 최소 개수를 구하자.

 

접근법

1. 동전 배열을 3개씩 끊어보면 100씩 곱해지는 규칙이 있다. 그리고 100단위 마다 필요한 최소 동전의 개수를 독립적으로 다른 100단위의 영향을 받지 않는다.

 

2. 따라서 100까지 필요한 동전의 최소 개수를 구하고, 100씩 나누어가며 결과를 계산하자. 

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int a[]={25,10},s[100]={0};
    f(i,1,100)s[i]=i;
    f(i,0,2)f(j,a[i],100)s[j]=min(s[j],s[j-a[i]]+1);
    
    int T;cin>>T;
    while(T--){
        long long price;cin>>price;
        int ans=0;
        while(price){
            ans+=s[price%100];
            price/=100;
        }
        cout<<ans<<'\n';
    }
    return 0;
}
 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.