1, 2, 3 더하기 9 (백준 16195)

안녕하세요. 오늘은 1, 2, 3 더하기를 해볼거예요.

문제

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

아이디어

dp[N][M]을 M개의 수를 사용해서 N을 만드는 경우의 수라고 합시다.
하지만 문제에서는 M개 이하의 수를 사용하라고 했으므로 DP[N][1~M]의 값을 출력해주면 됩니다.

소스코드

#include <iostream>
#include <algorithm>
using namespace std;

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

int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	dp[0][0] = 1;
	for (int i = 1; i <= 1000; i++)
	{
		for (int j = 1; j <= 1000; j++)
		{
			if (i >= 1) dp[i][j] += dp[i - 1][j - 1];
			if (i >= 2) dp[i][j] += dp[i - 2][j - 1];
			if (i >= 3) dp[i][j] += dp[i - 3][j - 1];
			dp[i][j] %= 1000000009;
		}
	}

	int T, N, M;
	cin >> T;
	while (T--)
	{
		cin >> N >> M;
		long long ans = 0;
		for (int j = 0; j <= M; j++)
			ans += dp[N][j];
		cout << ans % 1000000009 << "\n";
	}
}

감사합니다.