백준 1309 동물원

// 다시 풀기(힌트 얻어서 품)
 
// d[i][0] = 2*i에 사자를 배치하되 마지막 칸에는 배치하지 않는 경우
// d[i][1] = 2*i에 사자를 배치하되 마지막 칸 왼쪽에 배치하는 경우
// d[i][2] = 2*i에 사자를 배치하되 마지막 칸 오른쪽에 배치하는 경우
 
#include <cstdio>
using namespace std;
 
int n, d[100001][3];
 
int main() {
    scanf("%d", &n);
    d[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        d[i][0] = (d[i - 1][0] + d[i - 1][1] + d[i - 1][2]) % 9901;
        d[i][1] = (d[i - 1][0] + d[i - 1][2]) % 9901;
        d[i][2] = (d[i - 1][0] + d[i - 1][1]) % 9901;
    }
    printf("%d\n", (d[n][0] + d[n][1] + d[n][2]) % 9901);
    return 0;
}