세로길이 2, 가로길이n(n은 정수)인 벽면에, 2*1크기의 타일을 붙이는 방법의 가짓수 구하기(n은 1부터 들어올 수 있다.)

내가 작성한 코드(어드반스드 모두 통과)

let tiling = function (n) {
  // TODO: 여기에 코드를 작성합니다.
  // 문제 이해하기
  // 주어진 n은 타일로 채워야 하는 면적의 가로 길이. 세로 길이는 2이다. 
  // 구해야 하는 것: 2*1크기의 타일을 가지고 이 보드를 채우는 경우의 수.
  // 가로와 세로 어느 방향으로 놓아도 상관이 없다.

  // 예시 이해하기
  //조합 이용!
  if(n <=2) return n;
  //n이 3 이상인 경우
  /*
  가로가 0개일때: n개의 1을 서로 다른 방법으로 나열하는 가짓수
  가로가 1개일때: 1개의 2와, n - 1*2개의 1을 서로 다른 방법으로 나열하는 가짓수: n가지
  가로가 2개일때: 2개의 2와, n-2*2개의 1을 서로 다른 방법으로 나열하는 가짓수: 
  가로가 n/2개일때: n/2개의 2와, n-2*(n/2)개의 1을 서로 다른 방법으로 나열하는 가짓수
  */
  let sum = 0;
  for(let i = 0; i <= n/2; i++){ //i는 가로의 개수
    sum += factorial(n - i) / factorial(i) / factorial(n - 2 * i); //중복조합? 공식??
  }
  return sum;
};

function factorial(num){
  if(num === 0) return 1;
  return num * factorial(num - 1);
}

풀이 도출 과정

1시간 안에 다 못풀었다. 시작후 40분 경과했을때쯤, 애매하게 규칙을 안 상황에서 바로 코드를 자서 테스트를 했고, 에러가 나서 당황했다.

절대로, 규칙을 완전히 다 깔끔하게 정리하지 못한 상태에서 바로 코드를 짜려고 하지말자. 100%이해하고 짜도록 하자.

그리고 규칙 적을때, 엄청 깔끔하게 알아보기 쉽게 정리하자.

먼저, 입력값을 확인한다.

입력값은 벽면의 가로 길이이며, 1부터 시작한다.

출력값은 벽면을 타일로 덮는 방법의 가짓수이다.

입출력 예시를 보면, 4가 들어왔을 땐 5를 리턴하고, 2가 들어왔을 땐 2를 리턴한다고 나와있다.

그래서 이것을 그림으로 그려서 규칙을 찾아보고자 했다.

규칙을 정리하면 다음과 같다.