백준 1793 타일링 (파이썬)

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

1793번: 타일링

한 칸을 채우는 방법은 세로로 타일을 배치하는 방법 하나

두 칸을 채우는 방법은 가로로 타일을 2개 배치하는 방법과 2x2 타일을 배치하는 방법 2개

따라서 a[i] = a[i-1] + 2 * a[i-2]

import sys

input = sys.stdin.readline

def cnt(n):
    if n == 0 or n == 1:
        return 1
    a = [0 for _ in range(n+1)]
    a[0], a[1] = 1, 1
    for i in range(2, n+1):
        a[i] = a[i-1] + 2 * a[i-2]

    return a[n]

while True:
    try:
        print(cnt(int(input())))
    except:
        break