[이코테] 바닥공사

또 다른 다이나믹 프로그래밍 예제다. 난이도가 비교적 쉬웠다.

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다.

이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오.
예를 들어 2 X 3 크기의 바닥을 채우는 경우의 수는 5가지이다.

• 입력
  첫째 줄에 N이 주어진다. (1 <= N <= 1,000)

• 출력
  첫째 줄에 2 X N 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다.

• 입력 예시
  3

• 출력 예시
  5

# p223

n = int(input())
d1 = [0] * 1001


d1[0] = 1
d1[1] = 3

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