[BOJ] 16195 : 1, 2, 3 더하기 9 - travelbeeee

문제 : https://www.acmicpc.net/problem/16195

---

[ 알고리즘풀이 ]

dp[N][M] : N 을 M 개의 합으로 표현한 경우의 수.

dp[N][M] = dp[N - 1][M - 1] + dp[N - 2][M - 1] + dp[N - 3][M - 1];

#include<iostream>
#define M 1000000009
using namespace std;

int dp[1001][1001] = {}; // dp[N][M] : N을 M개로 표현

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	dp[1][1] = 1, dp[2][1] = 1, dp[2][2] = 1, dp[3][1] = 1, dp[3][2] = 2, dp[3][3] = 1;
	for (int i = 4; i <= 1000; i++) {
		for(int j = 2; j <= i; j++)
			dp[i][j] = ((dp[i - 1][j - 1] + dp[i - 2][j - 1]) % M + dp[i - 3][j - 1]) % M;
	}

	int t, n, m;
	cin >> t;
	while (t--) {
		cin >> n >> m;
		int sum = 0;
		for (int j = 1; j <= m; j++)
			sum = (sum + dp[n][j]) % M;
		cout << sum << '\n';
	}
	
	return 0;
}

---