[알고리즘] 3 x N 타일링

개요

바로 전에 풀었던 2 x N 타일링과 유사합니다.

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

프로그래머스

 

풀이

홀수의 경우는 타일을 가득 채울 수 없다는 것은 금방 알아챘는데 점화식을 구현해내는 과정이 상당히 어려웠다.

 

케이스에서는 4까지밖에 주어지지않았고 그 이상을 찾아보려고할 때 풀이가 전혀 생각나지 않았다.

다행히 질문하기에 케이스 몇개가 구해져있어서 그대로 가져와 구했다.

 

최대한 답을 안보고 하기위해 점화식까지 계산해서 작성했는데 값이 마이너스가 나올줄은 생각을 못했다.

 

큰 값에서 작은 값을 빼는데 마이너스가 나올 수 있는지 아무리 고민해봐도 풀리지않았다. 풀이 방법이 잘못된거같아 구글링을 좀 해보니 모듈러 연산때문이라고 하는데 여기서부터 조금 벅차서 여러 포스트 들을 참고했다. 구현 방법은 여러가지인거 같으니 스스로 이해할 수 있는 부분만 이해하고 넘어갔다. LV4짜리 문제였을줄은 몰랐다ㅎㅎ

프로그래머스 JAVA Level2: 3XN 타일링

/**
 * 3 * N짜리의 타일
 * n이 홀수인 경우엔 전부 채울 수 없다
 * 2 3
 * 4 11
 * 6, 41
 * 8, 153
 * 10, 571
 * 12, 2131
 * 14, 7953
 *
 * (n - 2) * 4 - (n - 4)
 */
function solution(n) {
  let answer = 0;
  //   const dy = Array.from({ length: n + 1 }, () => 0);
  const dy = Array(n + 1).fill(0);

  dy[1] = 0;
  dy[2] = 3;
  dy[3] = 0;
  dy[4] = 11;

  for (let i = 5; i <= n; i++) {
    if (i % 2 === 1) continue;
    const x = dy[i - 2] * 4 - dy[i - 4];
    dy[i] = x + (1000000007 % 1000000007);
  }

  answer = dy[n];

  return answer;
}

console.log(solution(100));