greentea31's Note

https://www.acmicpc.net/problem/1309

풀이 과정

d[i][k]를 2xi 우리에 사자를 가두는 경우의 수라고 하자. k = 0, 1, 2는 마지막 i번째 행에 사자가 없거나, 왼쪽에 있거나, 오른쪽에 있는 경우이다.

그러면,

d[i][0] = d[i-1][0] + d[i-1][1] + d[i-1][2]

d[i][1] = d[i-1][0] + d[i-1][2]

d[i][2] = d[i-1][0] + d[i-1][1]

의 점화식이 성립한다

소스 코드

"""
가로 세로 인접 x, 몇가지?

0, 1, 2 안두기 왼쪽 오른쪽, 9901은 나머지 처리 잘하기

"""

import sys

N = int(sys.stdin.readline())
mod = 9901

d = [[0, 0, 0], [1, 1, 1]]
for i in range(2, N+1):
    d.append([(d[i-1][0] + d[i-1][1] + d[i-1][2]) % mod, (d[i-1][0] + d[i-1][2]) % mod, (d[i-1][0] + d[i-1][1]) % mod])

print(sum(d[N]) % mod)