백준 1309 c++ : DP

#include <iostream>
#include <vector>
#include <algorithm>
#define MOD 9901

using namespace std;

int find_answer(int N) {
	cout << "find_answer()\n";
	int answer = 0;
	int i, j;
	vector<vector<int>> cage(N + 1, vector<int>(2, 0));
	cage[1][0] = 1;// 첫 줄에 사자가 한마리도 없는 경우
	cage[1][1] = 2;// 첫 줄에 사자가 있는 경우 (왼쪽, 오른쪽 배치 경우의 수 2)

	//사자가 가로, 세로로 붙어있게 배치 할 수 없음
	//사자를 배치하는 경우의 수

	//[i][0]은 한마리도 배치 안하는 경우
	//[i][1]는 한마리를 배치하는 경우
	for (i = 2; i <= N; i++) {
		cage[i][0] = (cage[i - 1][0] + cage[i - 1][1]) % MOD;
		cage[i][1] = (2 * cage[i - 1][0] + cage[i-1][1]) % MOD;
		cout << cage[i][0] << "\t" << cage[i][1] << "\n";
	}
	answer = (cage[N][0] + cage[N][1]) % MOD;

	return answer;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;

	cin >> N;
	cout << find_answer(N) << "\n";

	return 0;
}