[Python] 백준 1309 동물원

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

1309번: 동물원

 

코드 작성

n = int(input())
dp = [[0]*3 for _ in range(n+1)]
dp[0] = [1,1,1]
for i in range(1, n):
    dp[i][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] + dp[i-1][2]) % 9901
print(sum(dp[n-1])%9901)

코드  풀이

#1. 점화식

dp[n][0] : 첫 번째 칸에 채워졌을 때

dp[n][1] : 두 번째 칸에 채워졌을 때

dp[n][2] : 두 칸 모두 채워지지 않았을 때

 

#2. 초기값

dp[0]의 [0], [1], [2] 의 값을 각각 1로 세팅

 

#3. dp값 세팅

[[0,0,0], [0,0,0], [0,0,0] ... [0,0,0]]

 

#4. print

인덱스 0부터 시작했으므로 n-1값을 출력