[알고리즘] 바닥 타일 공사

바닥 타일 공사 문제

가로의 길이 N 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다.
1x2, 2x1, 2x2 덮개를 이용해 채우고자 한다. 바닥을 채우는 모든 경우의 수를 구하는 함수를 작성해보자.

입력 조건

1 <= n <= 1000

출력 조건

방법의 수를 796796으로 나눈 나머지를 출력한다.

체크할 점

1. 완전탐색으로 문제 해결이 가능한가?
   가능은 해 보인다. 해당 문제는 규칙이 존재한다. 2x2 타일은 3가지의 경우를 만들고 2x1 타일만 잘 조정하면 될 것 같긴하다.

2. 부분 문제로 분할이 가능하며 부분 문제의 답이 전체 정답에 포함 되는가?
   그러하다.

아래 그림으로 보는게 더 빠르게 이해할 수 있다.

구현

n = int(input())

def tile_bottom(n: int):
    d = [0] * (n+1)
    d[1] = 1
    d[2] = 3

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