[DP] 백준 1309 동물원

놓을 수 있는 건 1번 경우와 같이 X, 왼, 오

이렇게 3개 다 놓으려면 가장 아랫줄이 빈칸이어야 한다.

 그 외의 경우에는 2개를 놓을 수 있다.

빈칸인 경우는 n-2와 같다. 왜냐하면 빈칸은 모든 경우에 한번씩 들어가므로 n-1을 만들기위해 사용한 n-2에서 하나씩 만들어 졌기 때문

그외의 경우의 개수는 n-1에서 n-2의 경우를 빼준 것과 같다. 그 경우는 *2씩 해주면 되므로 

마이너스의 모듈러 연산에서는 연산결과가 -가 될 수 있기 때문에 그 경우 mod를 더해줘야 한다. 

#include <iostream>

#include <algorithm>

#include <cstring>

#include <limits.h>

#include <stack>

using namespace std;

typedef long long ll;

ll stb[10001]; // single table

ll sche[100001]; // single cache

int tb[1001][1001];

int cache[1001][1001];

int n,m;

const int mod = 9901;

int main(void) {

       

       cin >> n;

       sche[0] = 1;

       sche[1] = 3;

       for (int i = 2; i <= n; ++i) {

              

              int wow = sche[i - 1] - sche[i - 2];

              if (wow < 0) {

                     wow += mod;

              }

              

              sche[i] = (sche[i-2]*3)%mod  + (2*(wow))%mod;

       }

       cout << sche[n]%mod;

       

       

       return 0;

}