이코테_바닥공사

문제

가로의 길이가 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

풀이

이 문제는 n이 4일때까지 경우를 모두 일단 그려본 다음에 알았다. 타일을 채우는 경우의 수는 현재의 가로길이가 n이면 (n-2인 경우)x2 + (n-1인 경우) 이다. 덮개의 형태가 최대 2x2 이므로 바닥을 채울 수 있는 형태가 정해져 있기 때문에 이렇게 식을 세울 수 있다. 이해가 잘 되지 않는다면 직접 각 그려보며 확인해보면 이해가 될 것.(내가 그랬다..)

풀이코드

import sys
input = sys.stdin.readline

n = int(input())

d = [0] * 1001
d[0] = 0
d[1] = 1
d[2] = 3

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

print(d[n])