<Baekjoon>#1309 동물원 (Zoo) c++

이 문제는 앞에서 풀었던 RGB문제와 흡사하게 풀 수 있다.

먼저 동물원의 크기가 가로2 세로1인 경우를 생각해본다.
사자를 한 마리도 배치하지 않는 경우 + 왼쪽 우리에 배치하는 경우 + 오른쪽 우리에 배치하는 경우= 총 3가지가 있다.

다음 동물원의 크기가 가로2 세로2인 경우를 생각해본다.
두 번째 행만 봤을 때 사자를 한 마리도 배치하지 않는 경우는 가로2, 세로1일 때 사자를 배치하는 경우의 수의 합과 같다. (단지 우리 2칸이 생겼다고 생각한다)
왼쪽 우리에 배치하는 경우는 첫 번째 행에서 사자를 한 마리도 배치하지 않는 경우 + 오른쪽 우리에 배치하는 경우의 합과 같다.
오른쪽 우리에 배치하는 경우는 첫 번째 행에서 사자를 한 마리도 배치하지 않는 경우 + 왼쪽 우리에 배치하는 경우의 합과 같다.

#include<iostream>

const int MAX = 100001;
const int MOD = 9901;

using namespace std;

int makeDen(int n) {
	
	int dp[MAX][3];

	dp[1][0] = dp[1][1] = dp[1][2] = 1;
	
	for (int i = 2; i <= n; i++) {
		dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD;
		dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD;
		dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
	}

	return (dp[n][0] + dp[n][1] + dp[n][2])%MOD;
}


int main() {
	int n;

	cin >> n;
	if (n > MAX)
		exit(EXIT_FAILURE);

	cout << makeDen(n) << endl;

	return 0;
}