[백준][Python][1309][DP] 동물원

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

1309번: 동물원

DP 문제다.

 

예전에 풀어서 그런지 기억이 안났다.

 

이 문제는 n번째를 n-1, n-2 번째로 각각 나눠서 확인해야 한다.

 

n-1 번째에 [0,X][X,0] 일때 n 번째에서는 각각 [X,0][0,X] 할 수 있는 경우의 수가 있다.

그리고 n-1 번째에 아무것도 놓지 않는 방법의 수, [0,0] 의 수가 있다. 이 때는 어디든 놓을수 있다.

따라서, dp[n] = dp[n-1]* 2 + dp[n-2]의 경우의 수가 있다.

 

import sys


n = int(sys.stdin.readline())
dp = [1,3]
for i in range(2,n+1):
    dp.append(dp[i-2]+dp[i-1]*2)
    dp[i] = dp[i]%9901

print(dp[n])