[BOJ] 백준 9084 동전 c++ (DP)

문제 출처 : https://www.acmicpc.net/problem/9084

9084번: 동전

풀이

DP로 해결하였던 문제이다.

 

동전의 종류가 주어지고 주어진 금액을 만드는 모든 경우의 수를 세는 문제이다.

---

점화식은 다음과 같다.

for(int i = 0; i < N; i++)
	for(int j = coin[i]; j <= target; j++)
		dp[j] += dp[j - coin[i]];

 

---

 

#include <iostream>
#include <vector>

using namespace std;

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

	int T;
	cin >> T;
	while (T--){
		int dp[10000 + 1] = {0, };

		int N;
		cin >> N;
		vector<int> coin(N);
		int target;

		for(int i = 0; i < N; i++){
			cin >> coin[i];
		}

		cin >> target;

		dp[0] = 1;
		for(int i = 0; i < N; i++)
			for(int j = coin[i]; j <= target; j++)
				dp[j] += dp[j - coin[i]];

		cout << dp[target] << '\n';
	}	

	return 0;
}