Time Limit: 1s
Memory Limit: 128MB
2×n 안에 1×2 또는 1×1 타일을 채워넣는 방법의 수는 얼마인지 계산해보자.
Line 1: 입력 갯수 N (1 ≤ N ≤ 100)
Line 2~N+1: 가로 길이 n (1 ≤ n ≤ 20)
Line 1~N: 타일을 채우는 경우의 수를 출력한다.
3 2 3 5
7 22 228
2×2 안에 1×2 또는 1×1 타일을 채워넣는 방법은 7가지다.
직사각형을 채우는 방법의 수 = 맨 왼쪽위에 1×1 타일을 채우는 방법의 수 + 맨 왼쪽 위에 1×2 타일을 가로로 채우는 방법의 수 + 맨 왼쪽 위에 1×2 타일을 세로로 채우는 방법의 수
왼쪽 위가 한 칸 빈 직사각형을 채우는 방법의 수 = 맨 왼쪽 아래에 1×1 타일을 채우는 방법의 수 + 맨 왼쪽 아래에 1×2 타일을 채우는 방법의 수
왼쪽 위가 두 칸 빈 직사각형을 채우는 방법의 수 = 맨 왼쪽 아래에 1×1 타일을 채우는 방법의 수 + 맨 왼쪽 아래에 1×2 타일을 채우는 방법의 수