백준 15992번 1, 2, 3 더하기 7

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n과 m이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 단, 사용한 수의 개수는 m개 이어야 한다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n과 m이 주어진다. n은 양수이며 1,000보다 작거나 같다. m도 양수이며, n보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. 단, 사용한 수의 개수는 m개 이어야 한다.

D[n] = D[n-1] + D[n-2] + D[n-3] 에서 개수에 대한 차원 하나만 추가하면 됨.

D[n][m] = D[n-1][m-1] + D[n-2][m-1] + D[n-3][m-1] 이렇게..

그리고 중간에 % MOD를 먼저 해준건 값이커서 자료형 넘어가니까 미리한번 해준것..

#include<iostream>
#include <string.h>
#include<string>
#include<queue>
#include <vector>
#include<map>

using namespace std;

int MOD = 1000000009;
int D[1001][1001];
int N, M;
int main(void)
{
	D[1][1] = 1;
	D[2][1] = 1;
	D[2][2] = 1;
	D[3][1] = 1;
	D[3][2] = 2;
	D[3][3] = 1;

	for (int i = 4; i <= 1000; i++)
	{
		for (int j = 1; j <= 1000; j++)
		{
			D[i][j] = ((D[i - 1][j - 1] + D[i - 2][j - 1]) % MOD + D[i - 3][j - 1]) % MOD;
		}
	}

	int tc;
	cin >> tc;
	for (int t = 0; t < tc; t++)
	{
		cin >> N >> M;
		cout << D[N][M] << endl;
	}
	
	
}