[백준] 1309 '동물원' 파이썬(python)

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

1309번: 동물원

n = int(input())
dp = [[0, 0, 0] for _ in range(n+1)]
dp[1][0] = 1
dp[1][1] = 1
dp[1][2] = 1

for i in range(2, n+1):
    # no lion
    dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) % 9901
    # left lion
    dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % 9901
    # right lion
    dp[i][2] = (dp[i-1][0] + dp[i-1][1]) % 9901 
    
print(sum(dp[n]) % 9901)

Point

• dp테이블을 만든 뒤 이용하여 문제를 해결하는 DP 문제
• 세 가지의 경우를 나눌 수 있다. 사자가 안 놓인 경우, 사자가 왼쪽 칸에 놓인 경우, 사자가 오른쪽에 놓인 경우
• 사자가 안 놓인 경우는 이전에 경우 세가지를 모두 더 하고, 나머지는 똑같은 칸에 놓이면 안되기에 놓일 칸을 제외한 두가지를 더한다.