11727. 2 x n 타일링2

 

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 

이번에는 2 x n 직사각형을 2 x 1, 1 x 2에 추가로 2 x 2 타일로 채우는 방법의 수를 구하는 것이다.

 

마찬가지로 d[n]은

d[n] : 2 x n 직사각형을 2 x 1, 1 x 2, 2 x 2 타일로 채우는 방법의 총 가지 수

 

2 x n 타일링 1번 문제에서 2 x 2 타일만 추가됐다.

그리고 2 x 2 타일을 추가하는 건 그냥 1 x 2타일 두 개를 붙인 것과 같다.

 

d[n] = d[n - 1] + d[n - 2] + d[n - 2]

 

 

arr = [0] * 1001


def dp(a):
    if a <= 2: return a  # base check

    if arr[a] > 0: return arr[a]  # memoization

    arr[a] = dp(a - 2) + dp(a - 1)
    return arr[a]


n = int(input())  # 2 x n

for i in range(n + 1):
    arr[i] = dp(i)

print(arr[n] % 10007)

2 x n 타일링 1 문제에서 점화식만 살짝 바꾸면 된다.