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

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

2133번: 타일 채우기

2칸을 새로 채우는 경우는 3가지 이므로 a[i] = 3 * a[i-2]이다

4칸을 채우는 경우부터는 아래와 같은 타일이 생긴다

| = |

ㅡㅡ

4번째 전 값부터(i-4) 0까지 각각 2를 곱한 것을 반복문으로 더해나가면 처리할 수 있다

import sys

input = sys.stdin.readline

n = int(input())

a = [0 for _ in range(n+1)]
a[0] = 1
for i in range(2, n+1, 2):
    a[i] = a[i-2] * 3
    for j in range(i-4, -1, -2):
        a[i] += a[j] * 2

print(a[n])