바닥 공사

p. 223

 

n=int(input())

d=[0]*1001

d[1]=1
d[2]=3
for i in range(3, n+1):
  d[i]=(d[i-1]+2*d[i-2])%796796

print(d[n])

 

i-1칸을 채우는 방법 : 2x1타일 사용하기

 

i-2칸을 채우는 방법 : 1x2타일 사용하기, 2x2타일 사용하기, 2x1타일 사용하기 (i-1방식이 2개 있는 것과 같음 -> 중복))

 

점화식

d[i]= d[i-1] * 1 + d[i-2] * 2