[알고리즘] 2 x n 타일링 js

1. 개요

2 * n 직사각형이 주어질 때 1 * 2 타일을 꽉 차게 배치할 수 있는 모든 경우의 수를 찾는 문제이다.

 

프로그래머스

 

2. 풀이

처음 문제를 봤을 땐 모든 걸 탐색하라고 해서 DFS로 접근하려다가 수가 너무 크기도 해서 다른 방법을 조금 고민했다.

 

사실 이때 DFS가 안된다면 DP로 한번 생각해볼 수 있었는데 쉽게 생각을 못했다.

DP로 풀 경우는 아래와 같다

 

만약 n의 길이가 1일때를 생각해보자 2 * 1의 직사각형에는 타일을 세로로 하나밖에 넣지 못한다.

만약 n의 길이가 2라면 2 * 2 직사각형에는 타일을 세로로 2개 가로로 2개로 2가지 경우가 된다

2 * 3이라면 세로로 3개해서 1가지, 두개 눕히고 1개 왼쪽 오른쪽 배치해서 2가지가 나오니 경우가 3이 된다.

 

이렇게 계속 나아가다보면 dy[i] = dy[i-2] + dy[i - 1]이라는 식을 세울 수 있다.

 

구현해보면 아래와 같다

function solution(n) {
    const dy = Array.from({length: n+1}, () => 0)
  // const dy = Array(n + 1).fill(0);

  // 길이 1짜리 타일은 세로로 세워서 하나밖에 못옴
  dy[1] = 1;
  // 길이 2짜리 타일은 세로로 2개 잇기, 눕혀서 2개 쌓기로 2가지 방법임
  dy[2] = 2;

  // 조건 때문에 또 삽질
  for (let i = 3; i <= n; i++) {
    const x = dy[i - 2] + dy[i - 1];
    dy[i] = x % 1000000007;
  }

  return dy[n];
}JAVASCRIPT

효율성 검사에서 한번 걸러졌는데 Array.from으로 한 것은 실패라고 떴는데 Array fill은 통과가 됐다.

또 n + 1 배열로 만들어서 n 번째까지 검사했어야하는데 테스트 케이스는 통과 되길래 문제가 없는 줄 알았다.

마지막에 큰 수도 놓쳐서 문제를 좀 꼼꼼히 읽어야겠다