[백준] 1309 동물원 Python

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

1309번: 동물원

dp 는 3 * (n+1)의 공간으로 만들어 주었다. 

사자를 배치하는 것에 대해 생각해보면 다음과 같은 세 가지 이다. 

1. 사자를 배치하지 않는 경우 

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

2. 사자를 왼쪽 칸에 배치하는 경우 

사자를 연속해서 왼쪽 칸에 배치할 수 없으므로, 이전 계산 값 (dp[i-1])에서 오른쪽에 배치한 경우와 배치하지 않는 경우의 수를 가져온다. 

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

3. 사자를 오른 쪽 칸에 배치하는 경우 

사자를 연속해서 오른쪽 칸에 배치할 수 없으므로, 이전 계산 값 (dp[i-1])에서 왼쪽에 배치한 경우와 배치하지 않는 경우의 수를 가져온다. 

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

 

전체 코드 

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):
    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

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