https://www.acmicpc.net/problem/1309
1309번: 동물원첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.www.acmicpc.net
역시 식만 잘 잡으면 됨
칸이 2개 있으므로, 총 3가지 경우가 있음
안넣는경우, 왼쪽, 오른쪽
이를 dp[?][0],dp[?][0],dp[?][0] 로 정의함
맨 첫줄은 다 한가지 경우만 있으므로 1임
여서생각을 해보면
맨 마지막줄에 아무것도 안넣을려면, 그 전에 어케됬든 상관 x
dp[i][0]=sum(dp[i-1])
왼쪽에 넣을려면, 그 전줄에 안넣거나 오른쪽에 넣어야됨
dp[i][0]=dp[i-1][0]+dp[i-1][2]
오른쪽에 넣을러면, 안넣거나 왼쪽
dp[i][0]=dp[i-1][0]+dp[i-1][1]
메손실을 방지하기위해 더할때마다 %9901을 하고,
dp[i]를 모두 더해주면 됨
여기서 dp[i][1]과 dp[i][2]는 모두 같으므로
한번만해도 된다.
n=int(input())m=9901dp=[[0,0,0] for _ in range(n+1)]dp[1]=[1,1,1]
#안채울경우, 왼쪽에채울경우, 오른쪽에 채울 경우for i in range(2,len(dp)): dp[i][0]=sum(dp[i-1])%m
dp[i][1]=dp[i][2]=sum(dp[i-1][:2])%mprint(sum(dp[n])%m)