3×N 벽 타일 채우기
면접 대비시간 제한2초메모리 제한128 MB
3×N 벽을 2×1 도미노로 채우는 방법의 수를 N≤30 조건에서 구하는 문제입니다.
문제
세로가 3, 가로가 인 직사각형 벽이 있다. 이 벽을 또는 크기의 도미노 타일로 빈칸 없이 모두 채우려고 한다.
타일은 서로 겹치면 안 되고, 벽 밖으로 나가도 안 된다. 벽을 채울 수 있는 서로 다른 방법의 수를 구하라.
입력
첫째 줄에 정수 이 주어진다.
출력
첫째 줄에 벽을 타일로 채우는 경우의 수를 출력한다.
힌트
아래 그림은 벽을 타일로 채운 모습이다.
