타일링(Tiling) Javascript / 피보나치 유사

피보나치와 비슷한 타일링(Tiling) 문제

세로 길이2, 가로 길이 n인 2 x n 보드가 있습니다. 2 x 1크기의 타일을 가지고 이 보드를 채우는 모든 경우의 수를 리턴해야 합니다.

주의사항

타일을 가로, 세로 어느 방향으로 놓아도 상관없습니다. (입출력 예시 참고)

입출력 예시

let output = tiling(2);
console.log(output); // --> 2

output = tiling(4);
console.log(output); // --> 5
/* 
2 x 4 보드에 타일을 놓는 방법은 5가지
각 타일을 a, b, c, d로 구분

2 | a b c d
1 | a b c d 
------------

2 | a a c c
1 | b b d d 
------------

2 | a b c c
1 | a b d d 
------------

2 | a a c d
1 | b b c d 
------------

2 | a b b d
1 | a c c d 
------------
*/

우선 문제를 풀기에 앞서 규칙을 찾는게 중요하다고 생각했습니다.
n = 1, 오직 하나의 경우의 수만 존재합니다. (1개)
n = 2, 두 경우의 수가 존재합니다. (||, 二) (2개)
n = 3, 세 경우의 수가 존재합니다. (|||, |二, 二|) (3개)
n = 4, 다섯 경우의 수가 존재합니다. (|||| , ||二 , |二| , 二二, ||二) (5개)
n = 5, 여덟 경우의 수가 존재합니다.

따라서 n = 3 부터 피보나치 수열과 동일한 규칙성을 가지기 때문에 0,1,2에 대해서는 기본값을 설정해놓고 3부터는 재귀함수를 통해 문제를 풀면 됩니다.

function tiling (n) {
	// 기본값으로 설정된 배열
	const arr = [0, 1, 2];
    if(n <= 2){
    	return arr[n];
    }
    const fibo = (i) => {
      if(arr[i] !== undefined){
        return arr[i];
      }
      if(arr[i] <= 2){
        return arr[n];
      }
      arr[i] = fibo(i - 1) + fibo(i - 2);
      return arr[i];
    }
    return fibo(n);
}