[알고리즘] 타일링 알고리즘 문제

문제

2 x 1 크기의 타일로 세로 길이 2, 가로 길이 n인 2 x n 보드를 채우는 모든 경우의 수를 리턴하시오.

입력

타일의 가로 길이 n
(number 타입의 1 이상의 자연수)

출력

보드를 채우는 모든 경우의 수
(number 타입)

---

타일을 가로로 놓는 경우와 세로로 놓는 경우 두 가지를 생각해야 한다.

보드	타일
2 x 1	1
2 x 2	2
2 x 3	3
2 x 4	5
2 x 5	8

피보나치 수열과 유사하게 증가하고 있음을 확인할 수 있다.

배열 memo에 tiling(n)의 값을 저장하여 이미 도출된 값은 다시 구하지 않도록 한다.

---