[Lua] 백준 14852 타일 채우기 3

 

분할할 수 없도록 1칸을 채우는 경우가 2가지, 2칸을 채우는 경우가 3가지, 3칸,4칸...을 채우는 경우도 전부 2가지이므로

 

An=2*Sn-1+2+An-2를 풀면 된다.

dp={2,7}
dp[0]=1
n=io.read("*n")
for i=3,n,1 do
    dp[i]=(3*dp[i-1]+dp[i-2]-dp[i-3])%1000000007
end
io.write(dp[n])