다이나믹 프로그래밍: 바닥 공사

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다.

이 바닥을 1x2의 덮개, 2x1의 덮개, 2x2의 덮개를 이용해 채우고자 한다.

이때 바닥을 채우는 모든 경우의 수를 구하라.

 

n=int(input())

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

print(d[n])

d [i]=가로가 i일 때 바닥을 채우는 모든 경우의 수

 

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

 

가로가 i일 때..

"i-1까지의 것" + "2x1 짜리 타일 1개"로 구성할 수도 있고

"i-2까지의 것" + "2x2 짜리 타일 1개"로 구성할 수도 있고

"i-2까지의 것" + "1x2 짜리 타일 2개"로 구성할 수도 있다.

(i-2까지의 것 + 2x1 짜리 타일 2개로 구성하는 경우를 고려하지 않은 이유는... i-1까지의 것+2x1 짜리 타일 1개 에서 이미 고려되었기 때문이다)