[Python] 백준 1309 동물원

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

1309번: 동물원

 

 

문제 해결

뭔가 점화식 같은 느낌이 드므로 dp를 이용해야할 것 같다.

dp[1] = 3

dp[2] = 7

dp[3] = 17

dp[4] = 41 (예제 입출력에 존재)

뭔가 dp[n] = 2*dp[n-1] + dp[n-2] 처럼 보이는데... 논리적으로 설명을 못하겠다...

한번 시험해 봤는데

 

n = int(input())
if n == 1:
    print(3)
elif n ==2:
    print(7)
else:
    dp = [0 for _ in range(n+1)]
    dp[1] = 3
    dp[2] = 7
    for i in range(3,n+1):
        dp[i] = (2*dp[i-1] + dp[i-2])%9901
    print(dp[n])

 

성공!

 

하지만 논리적으로 설명하기가 힘들어서 더 세부적으로 dp를 짜보기로 했다.

dp[i][0] : i행까지 있는 우리에서 i행렬에 사자가 없을 경우의 수

dp[i][1] : i행까지 있는 우리에서 i행렬에 사자가 왼쪽열에 있을 경우의 수

dp[i][2]: i 행까지 있는 우리에서 i행렬에 사자가 오른쪽 열에 있을 경우의 수

 

그럼

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

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

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

간단하게 된다!

다 더해보니

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

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

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

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

성립이 된다!

그래서 위에 코드가 맞는 것이었다.

 

따라서 풀어서 코드를 쓰면

CODE

import sys
input = sys.stdin.readline

n = int(input())
dp = [[0]*3 for _ in range(n+1)]
dp[1][0] = 1 # 사자 배치 x
dp[1][1] = 1 # 사자 왼쪽 배치
dp[1][2] = 1 #  사자 오른쪽 배치
if n>=2:
    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 #2
        dp[i][2] = (dp[i-1][0] + dp[i-1][1])%9901 #2

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