[C/C++] 백준 - 2624번 : 동전 바꿔주기

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

2624번: 동전 바꿔주기

문제

명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 수 있다. 예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각 2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은 4가지 방법으로 교환할 수 있다.

• 20 = 10×2 
• 20 = 10×1 + 5×2 
• 20 = 10×1 + 5×1 + 1×5 
• 20 = 5×3 + 1×5

입력으로 지폐의 금액 T, 동전의 가지 수 k, 각 동전 하나의 금액 pi와 개수 ni가 주어질 때 (i=1, 2,…, k) 지폐를 동전으로 교환하는 방법의 가지 수를 계산하는 프로그램을 작성하시오. 방법의 수는 231-1을 초과 하지 않는 것으로 가정한다.

 

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 100000
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int T, k;
ll cache[10003][103];
vector<pair<int, int>> coin;

void input() {
	cin >> T;
	cin >> k;
	for (int i = 0; i < k; i++) {
		int value, cnt;
		cin >> value >> cnt;
		coin.push_back({ value, cnt });
	}
}

ll path(ll rest, ll index) {
	if (rest == 0) return 1;
	if (index == k) return 0;
	ll& ret = cache[rest][index];
	if (ret != -1) return ret;	
	ret = 0;
	for (int i = 0; i <= coin[index].second; i++) {
		if (rest - coin[index].first * i < 0) continue;
		ret += path(rest - coin[index].first * i, index + 1);
	}
	return ret;
}

ll solution() {
	memset(cache, -1, sizeof(cache));
	return path(T, 0);
}

int main() {
	fastio;
	input();
	cout << solution() << endl;

	return 0;
}