[백준/BOJ] 백준 1398번 : 동전 문제

www.acmicpc.net/problem/1398

1398번: 동전 문제

동전은 1,10,25,100,1000,2500... 순서이다. 그러므로 3개씩 잘라서 보면 (1,10,25), (100,1000,2500)...이다. 이 묶음들은 (1,10,25)에 뒤에 00개수의 차이이다. 그러므로 car % 100를 만드는데 필요한 1,10,25 동전의 최소 개수를 구하고, car /= 100으로 구한 금액 부분을 자르고 다시 car % 100를 만드는데 필요한 1,10,25 동전의 최소 개수를 구하는 과정을 car가 0이 될 때까지 반복해서 필요한 동전의 최솟값을 구한다.

 

코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int tc;
int coin[3] = { 25,10,1 };
int cache[100];

int Solve(int sum, int money)
{
	//money원을 만들었을때
	if (sum == money)
		return 0;

	//지금까지 구한 금액이 money를 넘어갈때 매우 큰 수를 반환
	if (sum > money)
		return 987654321;

	int& ret = cache[money - sum];

	//앞으로 money - sum 금액을 만드는 경우를 구한적이 있을때
	if (ret != -1)
		return ret;

	ret = 987654321;

	for (int i = 0; i < 3; i++)
	{
		ret = min(ret, Solve(sum + coin[i], money) + 1);
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int cnt;
	long long car;

	cin >> tc;

	memset(cache, -1, sizeof(cache));

	for (int t = 0; t < tc; t++)
	{
		cnt = 0;

		cin >> car;

		while (car != 0)
		{
			//car % 100 씩 잘라서 구한다
			//car % 100를 만드는데 필요한 25,10,1 동전의 최소 개수를 구한다
			cnt += Solve(0, car % 100);

			//구한 금액부분은 자른다
			car /= 100;
		}

		cout << cnt << "\n";
	}


	return 0;
}