[BOJ] 15992 : 1, 2, 3 더하기 7 - travelbeeee

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

---

[ 알고리즘풀이 ]

DP[N][M] : N을 M개의 1, 2, 3 의 합으로 표현하는 경우의 수.

→ DP[N][M] = DP[N - 1][M - 1] + DP[N - 2][M - 1] + DP[N - 3][M - 1];

#include<iostream>
#define MOD 1000000009

using namespace std;

int T, N, M, dp[1001][1001] = {};

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 = 1; j <= 1000; j++)
			dp[i][j] = ((dp[i - 1][j - 1] + dp[i - 2][j - 1]) % MOD + dp[i - 3][j - 1]) % MOD;
	}
	cin >> T;
	while (T--) {
		cin >> N >> M;
		cout << dp[N][M] << '\n';
	}
	return 0;
}

---