[프로그래머스 lev2/JS] 2 x n 타일링

문제 출처

프로그래머스 Lev2 - 2 x n 타일링

나의 풀이

1차 시도 (시간초과)

동적계획법이 필요한 것 같다.

function solution(n) {
  const ar = [1, 2];
  let tmp = [];
  let answer = 0;

  function dfs(sum) {
    if (sum > n) return;
    if (sum === n) {
      // console.log(tmp);
      answer++;
    } else {
      for (let i = 0; i < ar.length; i++) {
        tmp.push(ar[i]);
        dfs(sum + ar[i]);
        tmp.pop();
      }
    }
  }
  dfs(0);
  return answer % 1_000_000_007;
}

console.log(solution(4));

2차 시도 (통과)

재귀는 여전히 시간초과 발생하므로 동적계획법을 사용했다.
각 dy[i] 값마다 1_000_000_007을 % 연산해줘야 한다. 왜냐면 각 dy[i] 값 자체가 너무 커서 오류가 발생할 수 있기 때문이다.

function solution(n) {
  // function tiling(n) {
  //   if (n === 1) return 1;
  //   if (n === 2) return 2;
  //   else return tiling(n - 1) + tiling(n - 2) % 1_000_000_007;
  // }
  // return tiling(n);

  let dy = Array.from({ length: n + 1 }, () => 0);
  dy[1] = 1;
  dy[2] = 2;

  for (let i = 3; i <= n; i++) {
    dy[i] = (dy[i - 2] + dy[i - 1]) % 1_000_000_007;
  }

  return dy[n];
}

console.log(solution(4));