NAIAHD

2133_타일 채우기

출처 : 백준

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

알고리즘 풀이 방식:

import sys
sys.setrecursionlimit(10**6)

d = [0] * 1001
def dp(n):
    if n == 0 :
        return 1
    if n == 1:
        return 0
    if n == 2:
        return 3
    if (d[n]!=0):
        return d[n]
    result = 3 * dp(n-2)
    for i in range(3,n+1):
        if i % 2 == 0:
            result += 2 * dp(n-i)
    d[n] = result
    return d[n]

n = int(input())
print(dp(n))