[백준, node.js] 2133번 "타일 채우기" 문제 해결방법

[백준, node.js] 2133번 "타일 채우기" 문제 해결방법

문제

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

예제 입력 & 출력

입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다.

힌트

아래 그림은 3×12 벽을 타일로 채운 예시이다.

소스코드

기존에 타일 문제라고 생각하고, 간단히 생각했다가 바로 틀려버린 문제. 문제에 힌트가 있었던 이유가 있었다. DP 점화식을 만들기 위해 N=1, N=2...를 직접 만드는 과정에서 홀수의 경우 타일을 만들 수 없기 때문에 홀수 케이스의 경우 0으로 리턴하면 될 것이고, 짝수의 경우 N-2의 경우의 수 * 3만하면 끝나는 문제라고 생각했다.

오늘도 타이슨 좌 1승..

힌트를 유심히 살펴보면, N=4의 경우 중간에 끼어있는 예외 케이스가 존재한다는 사실을 깨닫게 된다.

N=4일 때 돌연변이 짜슥..

N=6일 때 돌연변이 짜슥..

각 케이스에 우리가 예상한 케이스 + (전체 돌연변이 케이스)를 더해주면 총 경우의 수가 된다.

const fs = require('fs');
let n = fs.readFileSync('./dev/stdin').toString();
n = Number(n);

// n 홀수의 경우
// 경우의 수 0
if (n % 2 !== 0) return console.log(0);

const dp = new Array(n+1).fill(0);
dp[0] = 1;
dp[2] = 3;

for (let i = 4; i <= n; i+=2) {
  dp[i] = dp[i-2] * 3;

  for (let j = 4; j <= i; j+=2) {
    dp[i] += dp[i-j] * 2;
  }
}

console.log(dp[n]);