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

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

---

[ 알고리즘풀이 ]

DP[0][X] = X를 1, 2, 3의 합으로 나타내는 방법 중 사용한 수의 개수가 짝수인 방법의 수

DP[1][X] = X를 1, 2, 3의 합으로 나타내는 방법 중 사용한 수의 개수가 홀수인 방법의 수

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

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

#include<iostream>
#define M 1000000009

using namespace std;

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

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

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

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

---