[Python] 백준 11727번: 2xn 타일링 2(DP)

문제

풀이

2x1의 직사각형을 타일로 채우는 방법은 타일을 세로로 새우는 방법 한 가지 이다.

2x2의 직사각형을 타일로 채우는 방법은 세 가지이다.

이 이후부터 i 는 i-1(전 것)에 막대기 하나를 붙인 경우와 i-2(전 전것)에 막대 두 개를 가로로 붙인 경우의 수, i-2에 2x2 타일을 붙인 경우의 수를 합친 것이 된다.

따라서 점화 식은 cache[i]=cache[i-1]+2*cache[i-2]가 된다.

n = int(input())

cache = [0 for _ in range(n+1)]

if n == 1:

    print(1)

    exit(0)

cache[1] = 1

cache[2] = 3

for i in range(3, n+1):

    cache[i] = cache[i-1]+2*cache[i-2]

print(cache[-1] % 10007)