BOJ 9084: 동전

#BOJ 9084: 동전

9084번: 동전

#풀이

 

음 이 문제는 정말 쉬운 문제라고 생각했지만 쉽지 않았다.... 뭔가 잡힐듯 안잡혀서 더욱더 화가 났다...

문제는 간단하게 m까지의 동전의 가지수를 구하는 것인데 

 

동전이 만약 1, 5, 7 로 22를 만들 수 있는 것을 생각하면

22 -1  : 21의 동전의 가지수

22 -5 : 17의 동전의 가지수

22 -7 : 16의 동전의 가지수

더하면 답이 나온다.

뭔가 간단하면서도 조금 간단하지 않은?? 그런 문제였다. 

일단 나는 처음에 1 (1,1) 을 다르게 생각해서 풀기 어려웠지만 다시 생각해보니 내가 틀렸다...

 

이거를 점화식으로 바꾸면

d[i] = d[i] + d[i - a[c]] 가 나온다!

 

#코드

#include<iostream> // #include<bits/stdc++.h>

using namespace std;

int t;
int n, m;
int coin[10005];
int ans[10005];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> t;
	while (t--) {
		cin >> n;
		for (int i = 0; i < 10005; i++)
			ans[i] = 0;

		for (int i = 1; i <= n; i++) {
			cin >> coin[i];
		}
		cin >> m;
		ans[0] = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = coin[i]; j <= m; j++) {
				ans[j] = ans[j]+ans[j - coin[i]];
			}
		}
		cout << ans[m] << '\n';
		
	}

	return 0;
}