백준 1309번 C++

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int MAX = 100001;
const int MOD = 9901;
int n;
int cache[MAX][3];

int lion() {
	cache[0][0] = cache[0][1] = cache[0][2] = 1;

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

int main(void) {
	cin >> n;

	cout << lion() << endl;
	return 0;
}