[DP] BOJ 15988번 1, 2, 3 더하기 3

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

15988번: 1, 2, 3 더하기 3

- 문제 파악

주어진 정수 n을 1, 2, 3의 합으로 나타낼 수 있는데 그 방법의 수를 출력하라.

 

- 정답

난 1, 2, 3이 더해지는 경우를 생각했다.

정수 n이 되기 위해 n - 1의 모든 경우의 수에 1을 더하면 n이 되고,

정수 n이 되기 위해 n - 2의 모든 경우의 수에 2를 더하면 n이 되고,

정수 n이 되기 위해 n - 3의 모든 경우의 수에 3을 더하면 n이 된다.

 

#include "bits/stdc++.h"

using namespace std;

int t;
int n;
unsigned long long D[1000005];

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> t;

	D[1] = 1;
	D[2] = 2;
	D[3] = 4;

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



	while (t--)
	{
		cin >> n;

		cout << D[n] << "\n";
	}

	

}