[BOJ 1398] 동전 문제

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

1398번: 동전 문제

 

- 문제 요약

 

구사과국은 동전만 사용하고, 동전의 가치는 다음과 같다.

1, 10, 25, 100, 1000, 2500, 10000, 100000, 250000, 1000000...

즉, 식으로 표현하면 K ≥ 0를 만족하는 모든 K에 대해서, 가치가 10K인 동전과 25×100K인 동전이 있는 것이다.

구사과국에 살고 있는 구사과는 초콜릿을 하나 구매해 5차원 세계로 이사 가려고 한다. 초콜릿의 가격이 주어졌을 때, 이를 구매하기 위해 필요한 동전 개수의 최솟값을 구해보자. 각 동전의 개수는 무한하고, 구매할 때는 정확하게 초콜릿의 가격만큼만 지불해야 한다.

 

 

- 알고리즘 정리

 

문제에서 주어진 동전의 가치를 보면 (1, 10, 25)의 동전에 100을 곱한 값이 계속 이어지고 있다는 걸 확인할 수 있습니다.

초콜릿의 가격이 주어졌을 때, 100으로 나눈 나머지를 보면 위에서 말한 (1, 10, 25)의 동전으로 지불해야 한다는 사실을 확인할 수 있습니다.

DP를 활용해서 해결하려면 초콜릿 가격(1~99)을 지불할 때 필요한 동전의 개수를 DP Table에 미리 저장해 둡니다.

그리고 가격을 100으로 나눈 나머지에 대해 필요한 동전 개수를 순차적으로 더해줍니다. (그리디)

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 100
typedef long long ll;
int t,dp[MAX];
ll result,a;

void f(){
	ll num=a%MAX;
	result+=dp[num];
	a/=MAX;
	if(a>0){
		f();
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>t;
	memset(dp,MAX,sizeof(dp));
	for(int i=0;i<MAX;i++){
		if(i>=25){
			dp[i]=min(dp[i-25]+1,dp[i-10]+1);
			dp[i]=min(dp[i],dp[i-1]+1);
		}
		else if(i>=10){
			dp[i]=min(dp[i-10]+1,dp[i-1]+1);
		}
		else{
			dp[i]=i;
		}
	}
	while(t--){
		cin>>a;
		result=0;
		f();
		cout<<result<<'\n';
	}
}

코드 제출 결과