백준 16195] 1,2,3 더하기 9

문제 출처)www.acmicpc.net/problem/16195

먼저 1,2,3 1개로 만드는 경우의 수는 1가지 씩이다.

이때 2를 2개로 만드는 경우의 수는 1을 1개로 만드는 경우에 1을 더하는 경우이므로 (1,1) 의 위치의 값을 가져 올 수 있다.

3을 2개로 만드는 경우의 수는 2를 1개로 만드는 경우에 1을 더하는 경우와 1을 1개로 만드는 경우에 2를 더하는 경우이므로 (2,1) + (1,1) = 2 의 값으로 만들 수 있다.

4를 2개로 만드는 경우의 수는 3을 1개로 반드는 경우에 1을 더하는 경우와 2를 1개로 만드는 경우에 2를 더하는 경우와 1을 1개로 만드는 경우에 3을 더하는 경우의 수 (3,1)+(2,1)+(1,1) = 3 으로 만들 수 있다.

 

따라서 n개의 값을 m개를 이용해서 만드는 경우는 dp[n][m] = dp[n-1][m-1] + dp[n-2][m-1] + dp[n-3][m-1] 의 점화식을 유도할 수 있다.

 

이렇게 테이블을 만들어 보면 다음과 같다.

 

여기서 7을 5이하로 만드는 경우의 수는 dp[7][1] ~dp[7][5] 까지의 합 37 을 계산할 수 있다.

 

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

long long dp[1001][1001] = {0}; 

int main() {

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

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

	return 0;
}