[백준 9084번] 동전 (C++)

문제링크 : https://www.acmicpc.net/problem/9084

#include <bits/stdc++.h> 
using namespace std;

int t, n, coin[21], m;
int dp[10001];

int main()
{
	cin >> t;
	while (t--)
	{
		memset(dp, 0, sizeof(dp));     //매 케이스마다 배열을 0으로 초기화
		dp[0] = 1;                     //처음 경우의 수는 무조건 1이므로 1로 초기화
		cin >> n;
		for (int i = 0; i < n; i++)
		{
			cin >> coin[i];
		}
		cin >> m;
		for (int i = 0; i < n; i++)
		{
			for (int j = coin[i]; j <= m; j++)
			{
				dp[j] += dp[j - coin[i]];      //각 동전이 가지는 경우의 수마다 배열에 더해줌 
			}
		}
		cout << dp[m] << "\n";
	}
}

규칙을 찾기가 너무 빡세서 검색을 참고했다.

막상 코드 자체는 쉬운편이지만 점화식을 떠올리기가 힘든 문제였다.