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

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

---

[ 알고리즘풀이 ]

DP[N] : N을 1, 2, 3으로 만드는 경우의 수.

DP[N] = DP[N - 1] + DP[N - 2] + DP[N - 3] 성립.

#include<iostream>
#define M 1000000009

using namespace std;

int N, K, dp[1000001] = { };


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

	dp[0] = 1, dp[1] = 1, dp[2] = 2, dp[3] = 4;
	for (int i = 4; i <= 1000000; i++)
		dp[i] = ((dp[i - 1] + dp[i - 2]) % M + dp[i - 3]) % M;

	int T, n;
	cin >> T;
	while (T--) {
		cin >> n;
		cout << dp[n] << '\n';
	}
	return 0;
}

---