[백준] 2133 타일 채우기 (파이썬)

문제

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

입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다.

해설

https://www.youtube.com/watch?v=kYoKLm8BZtI
유튜브에 자세히 설명이 되어있어 링크 추가합니다

코드

n = int(input())

li = [0]*(n+1)

if n==0:
    print(1)
elif n==1:
    print(0)
elif n==2:
    print(3)
else:
    li[0] = 1
    li[2] = 3
    for i in range(4,n+1,2):
        li[i] = li[i-2]*3
        for j in range(4,i+1,2):
            li[i] += li[i-j]*2
    print(li[n])