알고리즘/Baekjoon

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

개발하는 크롱 2020. 11. 25. 10:29
반응형

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

 

1398번: 동전 문제

김형택이 세운 나라의 화폐 체계는 단순하다. 이곳은 동전만 사용하고, 동전은 다음과 같이 다른 값을 가진다. 1, 10, 25, 100, 1000, 2500, 10000, 100000, ... 식으로 나타내면 0보다 크거나 같은 모든 K에

www.acmicpc.net

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;
}
반응형