171014_1309_동물원

#include <iostream> using namespace std; int main() {     int lion[100001][3]={0};     int N=0;          cin >> N;          lion[1][0]=1;     lion[1][1]=1;     lion[1][2]=1;          for(int i=2; i<=N; i++)     {         lion[i][0]=(lion[i-1][0]+lion[i-1][1]+lion[i-1][2])%9901;         lion[i][1]=(lion[i-1][0]+lion[i-1][2])%9901;         lion[i][2]=(lion[i-1][0]+lion[i-1][1])%9901;     }     cout << (lion[N][0]+lion[N][1]+lion[N][2])%9901; }

사자가 있는 방법 수를 3가지로 생각한다. -> lion[i][3] 으로 표현 

i번째 우리에 사자가 있는 방법

lion[i][0]	X	X
lion[i][1]	X	O
lion[i][2]	O	X

이에 따라 다음과 같은 점화식을 구할 수 있다.

        lion[i][0]=(lion[i-1][0]+lion[i-1][1]+lion[i-1][2]);

        lion[i][1]=(lion[i-1][0]+lion[i-1][2]);

        lion[i][2]=(lion[i-1][0]+lion[i-1][1]);