동물원 풀이

문제 링크: https://www.acmicpc.net/problem/1309

백준 알고리즘 기초 1/2 401에서 3번째 - 1309번 동물원을 풀어보았다.

 

풀이: dp[i]=2*dp[i-1]+dp[i-2]라는 점화식을 구해내면 된다.

 

C++

 

Python

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

Java