[백준 15990번] 1, 2, 3 더하기 5 (C++)

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

 

#include <bits/stdc++.h> 
using namespace std;

#define Mod 1000000009;  //나눠야 할 값 정의
int t, n;
long long dp[100001][4], result;
int main()
{
	cin >> t;
	dp[1][1] = dp[2][2] = dp[3][1] = dp[3][2] = dp[3][3] = 1;  //초기값
	while (t--)
	{
		cin >> n;
		for (int i = 4; i <= n; i++)  //위에서 3까지는 초기값을 정했기에 4부터 시작
		{
			dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % Mod;  //1의 자리에 대한 규칙
			dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % Mod;  //2의 자리에 대한 규칙
			dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % Mod;  //3의 자리에 대한 규칙
		}
		result = (dp[n][1] + dp[n][2] + dp[n][3]) % Mod;  //위에서 구한 각 자릿수를 더해서 결과값에 저장
		cout << result << "\n";
	}
	return 0;
}

값의 범위가 크기에 long long으로 선언했다.

점화식은 직접 경우의 수를 써보면서 확인했다.