https://www.acmicpc.net/problem/1793
2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×17 직사각형을 채운 한가지 예이다.
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 숫자 0 ≤ n ≤ 250이 주어진다.
입력으로 주어지는 각각의 n마다, 2×n 직사각형을 채우는 방법의 수를 출력한다.
dp = [1 for i in range(251)]
dp[2] = 3
for i in range(3,251,1):
dp[i] = dp[i - 1] + 2*dp[i - 2]
while True:
try:
n = int(input())
print(dp[n])
except:
break