타일링
면접 대비시간 제한1초메모리 제한128 MB
2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 여러 개의 n(최대 250)에 대해 구하는 문제입니다.
문제
2×n 직사각형을 2×1 타일과 2×2 타일만 사용해 빈칸 없이 채우는 방법의 수를 구하시오. 2×1 타일은 가로 또는 세로로 놓을 수 있으며, 타일은 서로 겹치거나 직사각형 밖으로 나갈 수 없다.
입력
입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 하나씩 주어지며, 정수 n이 주어진다.
출력
각 테스트 케이스마다 2×n 직사각형을 채우는 방법의 수를 한 줄에 하나씩 출력한다.
제한
- 0 ≤ n ≤ 250