#1309

#1309

문제

풀이

N=int(input())
dp=[[0] *3 for i in range(N)]

#0은 공백, 1은 왼쪽, 2는 오른쪽에 넣는다고 생각했을때
dp[0][0],dp[0][1],dp[0][2]=1,1,1

for i in range(1,N):
    dp[i][0]+=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%9901
    dp[i][1]+=(dp[i-1][0]+dp[i-1][2])%9901
    dp[i][2]+=(dp[i-1][0]+dp[i-1][1])%9901
    
    
result=(dp[N-1][0]+dp[N-1][1]+dp[N-1][2])%9901
print(result)

공백일 경우엔 전행이 0,1,2을 더해도 상관없다
그러나 왼쪽,오른쪽인 경우엔 반대 방향 혹은 공백으로 해줘야한다.

경우의 수가 dp[N-1]에 저장되어있으니 각각의 값을 모두 더해주면 우리에 동물을 넣을 수 있는 경우의 수가 출력된다.