[BOJ] (C++) 1309 동물원

DP를 이용한 문제였다.

각 row 별로 3개의 경우의 수가 있다.

0는 좌 우 모두 사자가 없는경우 1은 왼쪽만 있는경우 2는 오른쪽 있는 경우로 해서

반복문을 통하여 셋의 합을 통해 모든 경우의 수를 구하였다.

문제링크 : 1309번: 동물원 (acmicpc.net) 

#include <iostream>
#include <vector>

using namespace std;

#define MOD 9901

int main() {

	int N;
	cin >> N;

	vector<vector<int>> DP(N, vector<int>(3, 1));

	for (int i = 1; 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;
	}

	cout << (DP[N - 1][0] + DP[N - 1][1] + DP[N - 1][2]) % MOD << '\n';

	return 0;
}