[백준 1309] 동물원 (DP) (C/C++) (★★)

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
 
int N;
int dp[100010][3]; // 0(사자X), 1(사자 왼쪽), 2(사자 오른쪽)
 
int solve(int row, int status)
{
    if(row == N)
    {
        return 1;
    }
    
    if(dp[row][status] !=0)
    {
        return dp[row][status];
    }
    
    if(status == 0)
    {
        dp[row][status] += (solve(row+1, 0) + solve(row+1, 1) + solve(row+1, 2)) % 9901;        
    }
    else if(status == 1)
    {
        dp[row][status] += (solve(row+1, 0) + solve(row+1, 2)) % 9901;        
    }
    else if(status == 2)
    {
        dp[row][status] += (solve(row+1, 0) + solve(row+1, 1)) % 9901;    
    }
    
    return dp[row][status] % 9901;
}
 
int main(void)
{
//    freopen("B1309_input.txt", "r", stdin);
    
    cin >> N;
    
    cout << solve(0, 0);
    
    return 0;
}