[C++] 1309 - 동물원

문제 링크 : https://www.acmicpc.net/problem/1309

1309번: 동물원

 

 

 

#include<iostream>
 
#define MOD 9901
 
using namespace std;
 
int dp[100005] = {1, 3};
 
int main(void)
{
    int n;
    cin >> n;
 
    for(int i = 2; i <= n; ++i)
        dp[i] = (dp[i-2] + dp[i-1]*2)%MOD;
    
    cout << dp[n] << endl;
 
    return 0;
}