📖 문제

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다.
태일이는 이 얇은 바닥을 1 x 2의 덮개, 2 x 1의 덮개, 2 x 2의 덮개를 이용해 채우고자 한다.
이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오.

입력 조건

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

출력 조건

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

📝 풀이과정

• 덮개의 가로길이의 종류는 1, 2이기 때문에
  가로길이가 i인 바닥을 채우는 방법은 1)i - 1까지 채우고 나머지 2 x 1만큼을 채우는 것과, 2)i - 2까지 채우고 나머지 2 x 2만큼을 채우는 것이다.
• 2 x 2만큼을 채우는 방법에 2 x 1의 덮개 2개로 채우는 방법은 뺀 이유는 1)에 포함되기 때문이다.
• 따라서 dp[i] = 2 x dp[i - 2] + dp[i - 1]이다.

⌨ 코드

import sys

n = int(sys.stdin.readline().rstrip())

# DP 테이블 초기화
dp = [0] * 1001
dp[1] = 1
dp[2] = 3

for i in range(3, n + 1):
  # dp[i]는 2 x i크기의 바닥을 채우는 방법의 수
  dp[i] = (2 * dp[i - 2] + dp[i - 1]) % 796796

print(dp[n])