[Python] 바닥공사

문제

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

입력

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

출력

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

입력 예시

3

출력 예시

5

문제 풀이

• 바닥의 가로 크기가 1일 때 나올 수 있는 경우의 수는 1이다.
• 바닥의 가로 크기가 2일 때 나올 수 있는 경우의 수는 3이다.
• 바닥의 i - 1까지 타일로 채워진 경우 나올 수 있는 경우의 수는 1이다.
• 바닥의 i - 2까지 타일로 채워진 경우 나올 수 있는 경우의 수는 2 (1 * 2 로 채우는 경우는 앞에서 고려되었으므로 제외)
• 모든 경우를 구했으므로 796796으로 나눠 나머지를 구해야 한다.
• 따라서 점화식은 아래와 같다.

dp[i] = (dp[i - 1] + (2 * dp[i - 2])) % 796796

코드

n = int(input())
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 3
for i in range(3, n + 1):
    dp[i] = (dp[i - 1] + (2 * dp[i - 2] )) % 796796
print(dp[n])