바닥공사

 

문제

3가지 종류의 타일을 사용해 가로 N 세로 2인 바닥을 채울 때, 채울 수 있는 경우의 수를 구하라

 

 

유형파악 및 구현

타일의 종류는 2x1, 1x2, 2x2가 있다.

 

N이 1일 때,

경우의 수는 한가지 경우이다. 1x2

 

N이 2일 때,

경우의 수는 세가지 이다

(1x2, 1x2), (2x1, 2x1), (2x2)

 

N이 3일 때,

- (1x2, 2x1, 2x1), (1x2, 2x2) : N(1) + (2x1, 2x1) or (2x2)

- (1x2, 1x2, 2x1), (2x1, 2x1, 1x1), (2x2, 1x2) : N(2) + (1x2)

 

점화식을 만들어보면,

check[n] = check[n-1] + 2*check[n-2] 이다.

 

 

코드

n = 10000
check = [0]*(n+1)
check[1] = 1
check[2] = 3

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