[백준] 1309: 동물원 (Python)

문제📖

풀이🙏

• dp[i][0]의 경우는 i번째 행에 사자를 오른쪽에 배치하는 경우이므로 i-1번째 행에는 사자가 없거나 왼쪽에 위치할 수 있다.
• dp[i][1]의 경우는 i번째 행에 사자를 왼쪽에 배치하는 경우이므로 i-1번째에 사자가 없거나 오른쪽에 위치할 수 있다.
• dp[i][2]의 경우는 i번째 행에 사자를 배치 안하는 경우므로 i-1번째에 어느 위치에 사자가 있어도 상관없다.

코드💻

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

for i in range(3):
    dp[1][i] = 1

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

print(sum(dp[n])%9901)