[BOJ 1398 // C++] 동전 문제

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1398번 문제인 동전 문제이다.
문제는 아래 링크를 확인하자.

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

1398번: 동전 문제

작은 자릿수부터 두 자리씩 끊어읽을 때, 그 두자리 수를 1, 10 및 25를 이용해 구성하기 위해 필요한 최소 동전 수를 구해 더해나가는 것으로 문제를 해결하자.

 

이는 각 두 자리수에 25를 0개, 1개, 2개 및 3개 사용하고 남은 수의 각 자릿수의 합만큼 1 및 10을 이용해 두 자리수를 구성해보는 것으로 구할 수 있다. 또는 knapsack dp를 이용해 0 이상 100 미만의 정수에 대해 필요한 최소 동전 개수를 미리 전처리해두는 것도 좋다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int T;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> T;
	while (T--) {
		int ans = 0;
		ll x; cin >> x;
		while (x) {
			int cur = x % 100;
			x /= 100;
			int tmp = 1000000007;
			int cnt = 0;
			while (cur >= 0) {
				tmp = min(tmp, cur / 10 + cur % 10 + cnt);
				cur -= 25, cnt++;
			}
			ans += tmp;
		}

		cout << ans << '\n';
	}
}