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

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

---

[ 알고리즘풀이 ]

DP[N] : N 을 1, 2, 3의 합으로 대칭을 이루며 표현하는 경우의 수

→ DP[N] = DP[N - 2] + DP[N - 4] + DP[N - 6];

( 기존의 표현 방법에다가 양쪽 끝에 1 , 1 / 2, 2 / 3, 3 을 추가하면 된다. )

#include<iostream>
#define M 1000000009

using namespace std;

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

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

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

---