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

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

---

[ 알고리즘풀이 ]

DP[0][N] : N을 같은 수를 두 번 이상 연속해서 사용안하고 끝이 1로 끝나는 경우.

DP[1][N] : N을 같은 수를 두 번 이상 연속해서 사용안하고 끝이 2로 끝나는 경우.

DP[2][N] : N을 같은 수를 두 번 이상 연속해서 사용안하고 끝이 3로 끝나는 경우.

→ DP[0][N] = DP[1][N - 1] + DP[2][N - 1];

→ DP[1][N] = DP[0][N - 2] + DP[2][N - 2];

→ DP[2][N] = DP[0][N - 3] + DP[1][N - 3];

#include<iostream>
#define M 1000000009

using namespace std;

int T, N, dp[3][100001] = {};

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

	dp[0][1] = 1, dp[1][2] = 1, dp[0][3] = 1, dp[1][3] = 1, dp[2][3] = 1;
	for (int i = 4; i <= 100000; i++) {
		dp[0][i] = (dp[1][i - 1] + dp[2][i - 1]) % M;
		dp[1][i] = (dp[0][i - 2] +  dp[2][i - 2]) % M;
		dp[2][i] = (dp[0][i - 3] + dp[1][i - 3]) % M;
	}
	cin >> T;
	while (T--) {
		cin >> N;
		cout << ((dp[0][N] + dp[1][N])% M + dp[2][N])% M << '\n';
	}
}

---