• 2 * n의 타일을 채우는 경우의 수는 피보나치 수열의 로직과 동일하다.
  • 재귀적으로 f(n) = f(n-1) + f(n-2)를 돌려준다.
• Dynamic Programming으로 해결 가능하다.

let tiling = function (n) {
  /*
  1. n=0 -> 0개
  2. n=1 -> (a, b) -> 1개
  3. n=2 -> (ab, ab), (aa, bb) -> 2개
  4. n=3 -> (abc, abc), (aac, bbc), (aab, ccb) -> 3개
  5. n=4 -> (abcd, abcd), (aabb, ccdd), (accd, abbd), (abcc, abdd), (aacd, bbcd) -> 5개
  6. 피보나치 수열의 로직이랑 동일하다. -> n이 2이하일때는 n과 동일한 값 출력
  f(0) = 0
  f(1) = 1
  f(2) = 2 = f(1) + f(0)
  f(3) = 3 = f(2) + f(1)
  f(4) = 5 = f(3) + f(2)
  */

  // 메모이제이션 써보자
  let memo = [];
  
  const recursive = (n) => {
    if(n <= 2) {
      return n;
    } else {
      // memo에 값이 있으면
      if(memo[n] !== undefined) {
        return memo[n];
      } else {
        // 피보나치랑 같은 로직
        memo[n] = recursive(n-1) + recursive(n-2);
        return memo[n];
      }
    }
  };
  return recursive(n);
};