[이코테] 바닥 공사

문제

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

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

입력 조건

첫째 줄에 N이 주어진다. ($1 \leq N \leq 1,000$)

출력 조건

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

입출력 예

Example 1:

Input: 
3
Output: 
5

풀이과정

책 풀이

1. 왼쪽부터 I - 1까지 길이가 덮개로 이미 채워져 있으면 2 x 1의 덮개를 채우는 하나의 경우밖에 존재하지 않는다.
2. 왼쪽부터 i - 2까지 길이가 덮개로 이미 채워져 있으면 1 x 2 덮개 2개를 넣는 경우, 혹은 2 x 2의 덮개 하나를 넣는 경우로 2가지 경우가 존재한다.

왼쪽부터 N - 2 미만의 길이에 대해서는 고려할 필요가 없다. 왜냐하면 사용할 수 있는 덮개의 형태가 최대 2 x 2의 직사각형 형태이기 때문이다. 다시 말해 바닥을 채울 수 있는 형태는 위에서 언급한 경우밖에 없다. 따라서 다음과 같이 점화식을 세울 수 있다. \(a_{i} = a_{i-1} + a_{i-2} \times 2\) 왼쪽부터 N - 2까지 길이가 덮개로 이미 채워져 있는 경우 덮개를 채우는 방법은 2가지 경우가 있다. 이 두 방법은 서로 다른 것이므로, 결과적으로는 $a_{i}$는 $a_{i-1}+a_{i-2}+a_{i-2}$가 된다. 따라서 이를 간략히 $a_{i} = a_{i-1} + a_{i-2} \times 2$로 표현한 것이다.

# 정수 N을 입력받기
n = int(input())

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0]*1001

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
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])