백준 1398: 동전 문제 (C++)

문제 링크: www.acmicpc.net/problem/1398

1398번: 동전 문제

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

화폐단위가 100씩 곱한 값으로 끊어진다는 것을 캐치하면 쉽게 풀리는 문제이다.

현재 지불해야하는 금액 중 100으로 나눈 나머지는 어차피 100 이하의 금액인 동전(1, 10, 25)로만 지불할 수 밖에 없다.

따라서 1~99 금액에 대한 필요한 동전 개수를 계산해 dp배열에 저장해두고 지불해야 하는 금액의 100으로 나눈 나머지에 대해 필요한 동전 개수를 더해나간다.

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int t; // 테스트케이스 개수
long long ans;
long long price;
int dp[100]; 

// dp 배열 값 계산
void calc() {
	for (int i = 0; i < 100; 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;
		}
	}
}

// 화폐 단위가 100단위로 곱해진다는 것에 주목 {1,10,25}*(100^k)
void solve() {
	long long tmp = price % 100;
	ans += dp[tmp];
	price /= 100;
	if (price > 0) {
		solve();
	}
}

int main() {
	// dp 배열 계산하고 시작
	memset(dp, 100, sizeof(dp));
	calc();

	scanf("%d", &t);
	for (int i = 0; i < t; i++) {
		scanf("%lld", &price);
		ans = 0;
		solve();
		printf("%lld\n", ans);
	}

	return 0;
}