[Algorithm], tiling, 피보나치 활용

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

입력 인자 : n

• number 타입의 1 이상의 자연수

출력

• number 타입을 리턴한다.

주의사항

• 타일을 가로, 세로 어느 방향으로 놓아도 상관 없다.

let tiling = function (n) {
  let result = [1, 1];
  for (let i = 2; i <= n; i++) {
    if (n < 2) {
      return result[n]
    }
    result[i] = result[i-1] + result[i-2];
  }
  return result[n];
}:

문제를 살펴보면,

n이 1일때 타일은 세로로 1개.

n이 2일때 타일은 l l, = 2개.

n이 3일때 타일은 l l l, l =, = l 3개,

n이 4일때 타일은 l l l l, l l =, = l l, = =, l = l 5개,

.

.

.

규칙성을 볼 때 피보나치의 수열대로 나가는걸 볼 수 있다.