[DP] 1309 - 동물원 (실버1) with Python

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

1309번: 동물원

주저리 주저리

개인적으로 조금 시간이 많이 걸렸던 문제였다.
2 * n 타일링이 생각나는 그 문제
다른 점이라고 하면 사자는 서로 겹치지 않아야하고 아예 배치도 안 할수도 있다는 문제이다.
일단 문제를 보고 처음엔 규칙이 있나 확인해 보았지만 규칙이 보이지는 않았다.
즉 수열같은 규칙은 아니라는 말이고... 그럼 문제 자체를 들어가 봐야겠다.

문제 해결

저 가로 2칸 네모안에 왼쪽, 오른쪽 둘 중 하나에 배치를 할 수 있고, 배치도 안할수가 있다.
그렇게 생각해보면 위에서 배치를 안하는 케이스, 위에서 왼쪽에 배치를 한 케이스, 위에서 오른쪽에 배치를 한 케이스를 나눌 수가 있다.

dp[n][1] = dp[n-1][0] + dp[n-1][2] # 위에서 왼쪽에 배치한 경우
dp[n][2] = dp[n-1][0] + dp[n-1][1] # 위에서 오른쪽에 배치한 경우

만약 위에가 비어있는 케이스라면 밑에서는 왼, 오, 그리고 안 둘 수 있는 3가지의 경우가 있다.

dp[n][0] = dp[n-1][0] + dp[n-1][1] + dp[n-1][2]

코드

import sys
input = sys.stdin.readline
n = int(input())
mod = 9901
dp = [[0 for _ in range(3)] for _ in range(n+1)]
dp[1][0] = 1
dp[1][1] = 1
dp[1][2] = 1
for i in range(2,n+1):
    dp[i][0] = (dp[i-1][1] + dp[i-1][2] + dp[i-1][0])%mod
    dp[i][1] = (dp[i-1][0] + dp[i-1][2])%mod
    dp[i][2] = (dp[i-1][0] + dp[i-1][1])%mod
print(sum(dp[n])%mod)