Algorithm 16 : tiling

설명

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

예시

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 
------------
*/

생각

2x1 타일을 가지고 가로길이가 1씩 늘어날 때마다 경우의 수 를 세보았다. 그 결과 1,2,3,5,8 의 수를 가진다는 것을 알 수 있었고 점화식 형태로 문제를 풀면 되겠다고 생각했다.

풀이

let tiling = function (n) {
  // TODO: 여기에 코드를 작성합니다.
  //점화식으로 해결
  //빈 배열에 점화식 값들을 넣고 거기서 출력하기 -> 시간복잡도 개선에 좋을 듯
  let output = []
  output[1] = 1
  output[2] = 2
  for (let i = 3; i <= n; i++) {
    output[i] = output[i - 2] + output[i - 1]
  }
  return output[n]
};

깨달은 점

예시를 처음부터 하나씩 나열하면서 규칙을 찾아보자.
규칙을 찾으면 시간복잡도를 개선할 수 있는 방법을 생각해보자 -> 대표적인 방법들을 공부하기