프로그래머스 lv2 3n 타일링

1. 개요

• https://school.programmers.co.kr/learn/courses/30/lessons/12902

2. 풀이

def solution(n):
    N = 5001
    
    if n&1:
        return 0
    
    DB, DB[0], DB[2] = [0]*(N), 0, 3
    
    for i in range(4, n+1, 2):
        # DB[2] 뒤에 붙이는경우
        # 특수케이스를 앞에두고 나머지를뒤에 붙이는 경우
        # 새로운 특수케이스 2개
        DB[i] = DB[2]*DB[i-2] + 2*sum(DB[i-j] for j in range(4, i+1, 2)) + 2

    return DB[n]