Toy#5 tiling

문제

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

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

Advanced
타일링 문제를 해결하는 효율적인 알고리즘(O(N))이 존재합니다. 반드시 직접 문제를 해결하시면서 입력의 크기에 따라 어떻게 달라지는지 혹은 어떻게 반복되는지 관찰하시기 바랍니다.

풀이

1. 코드 작성 전에 일단 경우의 수 파악 먼저 시도

  
1. 세로 2 x 가로 1 보드: 총 1가지

2. 세로 2 x 가로 2 보드: 총 2가지

   2-1. 세로가 0개 일때 -> 경우의 수 1가지
        - - 
        - - 
   2-2. 세로가 1개 일때 -> 경우의 수 0가지
   2-3. 세로가 2개 일때 -> 경우의 수 1가지
   
        | | 
        | | 

3. 세로 2 x 가로 3 보드: 총 3가지

   3-1. 세로가 1개 일때 -> 경우의 수 2가지

     1. | - -
        | - -
       
     2. - - |
        - - |   
       
   3-2. 세로가 2개 일때 -> 경우의 수 0가지
   3-2. 세로가 3개 일때 -> 경우의 수 1가지
   
       | | |
       | | |

4. 세로 2 x 가로 4 보드: 총 5가지

   4-1. 세로가 0개 일때 -> 경우의 수 1가지
       - - - -   
       - - - -

   4-2. 세로가 1개 일때 -> 경우의 수 0가지
   4-3. 세로가 2개 일때 -> 경우의 수 3가지

     1. | | - - 
        | | - -

     2. | - - |
        | - - |

     3. - - | |
        - - | |

   4-4. 세로가 3개 일때 -> 경우의 수 0가지
   4-5. 세로가 4개 일때 -> 경우의 수 1가지
   
       | | | |
       | | | |

5. 세로 2 x 가로 5 보드: 총 8가지

   5-1. 세로가 1개 일때 -> 경우의 수 3가지

     1. | - - - - 
        | - - - - 

     2. - - | - -
        - - | - -
   
     3. - - - - |
        - - - - |

   5-2. 세로가 3개 일때 -> 경우의 수 4가지

     1. | - - | |
        | - - | |

     2. | | - - |
        | | - - |

     3. | | | - -
        | | | - -

     4. - - | | |
        - - | | |

   5-3. 세로가 5개 일때 -> 경우의 수 1가지

      | | | | |
      | | | | |

✅ 경우의 수를 정리해보면, 아래와 같음

가로 1 ➡️ 1가지
가로 2 ➡️ 2가지
가로 3 ➡️ 3가지
가로 4 ➡️ 5가지
가로 5 ➡️ 8가지

---

2. 익숙한 저 숫자들은 혹시...피보나치..?

let tiling = function (n) {

  let arr = [1, 2];
  
  for(let i = 2; i < n; i++){
    arr[i] = arr[i-2] + arr[i-1]; 
  }
  
  // index 값은 0부터 시작이니까 -1
  return arr[n - 1];
};

/*

n=5

1. for문 실행

i=2
arr[2] = arr[0] + arr[1] = 3

i=3
arr[3] = arr[1] + arr[2] = 5

i=4
arr[4] = arr[2] + arr[3] = 8

=> arr = [1, 2, 3, 5, 8]

2. for문 종료 return arr[5 - 1] = 8

*/

---

3. 레퍼런스 코드: dynamic with memoization( O(N))

let tiling = function (n) {
  const arr = [0, 1, 2];

  const getTile = (index) => {
    if (arr[index] !== undefined) return arr[index];
    if (index <= 2) return arr[n];
    arr[index] = getTile(index - 1) + getTile(index - 2);
    return arr[index];
  };
  return getTile(n);
};

/*
n=5

1. getTile(5) => index=5
arr[5] = undefined 니까 첫번째 if문 pass
index가 2보다 크니까 두번째 if문도 pass
arr[5] = getTitle(4) + getTitle(3)

  1-1. getTitle(4) => index=4
  arr[4] = undefined 니까 첫번째 if문 pass
  index가 2보다 크니까 두번째 if문도 pass
  arr[4] = getTitle(3) + getTitle(2)

    1-1-1. getTitle(3) => index=3
    arr[3] = undefined 니까 첫번째 if문 pass
    index가 2보다 크니까 두번째 if문도 pass
    arr[3] = getTitle(2) + getTitle(1)

      1-1-1-1. getTitle(2) => index=2
      arr[2] = 2 => 첫번째 if문 실행 => return arr[2] => 2를 리턴

      1-1-1-2. getTitle(1) => index=1
      arr[1] = 1 => 첫번째 if문 실행 => return arr[1] => 1를 리턴

    arr[3] 
    = getTitle(2) + getTitle(1)
    = 2 + 1 
    = 3

    1-1-2. getTitle(2) => index=2
    arr[2] = 2 => 첫번째 if문 실행 => return arr[2] => 2를 리턴

  arr[4] 
  = getTitle(3) + getTitle(2)
  = 3 + 2
  = 5

arr[5] 
= getTitle(4) + getTitle(3)
= arr[4] + arr[3]
= 5 + 3
= 8

=> arr = [0, 1, 2, 3, 5, 8]

*/