백준1309(파이썬) - 동물원

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

1309번: 동물원

• 이 문제를 읽고 처음 든 생각은 'Bottom-up 방식의 DP문제' 였다.
• 가장 유명한 타일 채우기 문제 처럼 점화식을 구해서 메모이제이션 기법을 사용해서 구현한 이전 DP값을 가져다가 쓰는 문제였고, 점화식은 어렵지 않게 생각할 수 있었다. 아래와 같이 점화식을 세울 수 있다.

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

 

전체 코드는 아래와 같다.

import sys
input = sys.stdin.readline

n = int(input())

dp = [0]*(n+1)

dp[0] = 1
dp[1] = 3
for i in range(2,n+1):
    dp[i] = 2*dp[i-2]+dp[i-1]+(dp[i-1]-dp[i-2])
    dp[i] %= 9901
print(dp[-1])