동물원 ( 1309 번 )

1309번: 동물원

 

🧠 알고리즘

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[n-1]에 저장하고 마지막에 sum(dp[-1]) % 9901로 반환

 

🧾 코드

import sys

def _main(n):
    """ [0, 0, 0] >>> [no 배치, 오른쪽 배치, 왼쪽 배치] """
    dp = [[0, 0, 0] for _ in range(n)]
    dp[0][0], dp[0][1], dp[0][2] = 1, 1, 1

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

    return sum(dp[-1]) % 9901
    
n = int(sys.stdin.readline().rstrip())

print(_main(n))

 

⏱️ 시간 복잡도

for idx in range(1, n) : n 번의 점화식 순회 ( 선형 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )