[1309] 동물원

http://boj.kr/1309

d[n][k] : n번째 줄에 상태가 k일 때, n번째 줄까지 사자를 배치할 수 있는 경우의 수

- 소스코드

#include <stdio.h>
#define MOD 9901
 
int d[100001][3];
 
int go(int n, int k)
{
    int a, b;
    if(n == 0) return 1;
    if(d[n][k]) return d[n][k];
 
    a = go(n-1, (k+1)%3);
    b = go(n-1, (k+2)%3);
    
    if(k == 0) a += go(n-1, 0);
 
    return d[n][k] = (a+b)%MOD; 
}
 
int main()
{
    int n;
    scanf("%d", &n);
    printf("%d\n", go(n, 0));
    return 0;
}

>> k = 0 인 경우는 둘 다 비워있는 상태.

>> k = 1 인 경우는 사자를 왼쪽에 배치, k = 2 인 경우는 사자를 오른쪽에 배치한 상태