문제

2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

import sys

input = lambda: sys.stdin.readline().strip()

d = [0] * (251)
d[0], d[1], d[2] = 1, 1, 3

def tile(i):
  if d[i] != 0:
    return d[i]
    
  if d[i-1] == 0:
    d[i-1] = tile(i-1)
  if d[i-2] == 0:
    d[i-2] = tile(i-2)
  d[i] = d[i-1] + d[i-2] * 2
  return d[i]

while True:
  try:
    n = int(input())
    tile(n)
    print(d[n])
  except:
    break

백준 1793 타일링