[백준] 1309 동물원 Python

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

1309번: 동물원

 

일단 이 문제를 풀기 위해서 N이 각각 1, 2, 3 일 때를 생각해봤다. 

 

N = 1일 때는

사자

사자

이렇게 생겼고 

 

N = 2 일 때는

N = 1에서 아무 사자 없는 두 칸을 붙이거나 

사자가 한마리 있는 두 칸을 붙인 듯이 이루어져있다.

 

N = 3

일 때는

N = 2일 때 아무 사자 없는 두 칸을 붙일 때 즉 7개

N = 1일 때 아무 사자 없는 두 칸과 사자가 한 마리가 있는 두 칸을 붙일 때 즉 3 * 2개

N = 2일 때 사자가 제일 위에 한 마리 있을 때 사자 한마리 있는 두 칸을 붙일 때 즉 7 - 3개

를 다 더한 7 * 2 + 3 = 17개이다. 

 

 

여기서

dp[i] = dp[i-2] + dp[i-1] * 2이라는 점화식을 만들 수 있다.

 

N = int(input())
dp=[3, 7]
for i in range(2 , N) :
    dp.append(dp[i-1]*2%9901+dp[i-2]%9901)
print(dp[N-1]%9901)

위에서 구한 점화식을 이용해서 위와 같은 코드를 만들었다.