토이 5번

문제

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

풀이

let tiling = function (n, m = []) {
  // TODO: 여기에 코드를 작성합니다.
  // 2 => 2 / 4 => 5  5 =>
  // 0 1 1 2 3 5 8 13
  // 피보나치 수열 조합을 보임 
  // 빈배열에 해당 하는 숫자를 채워넣는다.

  let result = 0;
  
  if(n <= 3){
    return n;
  }
  if(m[n] !== undefined){
    return m[n]
  }
  result = tiling(n-1, m) + tiling(n-2, m)
  m[n] = result;

  return result;

};

초고수 풀이

let tiling = function (n) {
  // 인덱스를 직관적으로 관리하기 위해
  // 앞 부분을 의미없는 데이터(dummy)로 채운다.
  const memo = [0, 1, 2];

  // 재귀를 위한 보조 함수(auxiliary function)을 선언)
  const aux = (size) => {
    // 이미 해결한 문제는 풀지 않는다.
    if (memo[size] !== undefined) return memo[size];
    if (size <= 2) return memo[n];
    memo[size] = aux(size - 1) + aux(size - 2);
    return memo[size];
  };
  return aux(n);
};