백준 - 타일채우기3(14852번) - 파이썬(python)

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

14852번: 타일 채우기 3

 

import sys
input=sys.stdin.readline


dp=[0 for _ in range(1000001)]
dp2=[0 for _ in range(1000001)]

n=int(input().rstrip())

dp[0]=0
dp[1]=2
dp[2]=7

dp2[1]=1
dp2[2]=dp[0]+dp2[1]


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


print(dp[n])