백준 2133 JavaScript

문제

백준 2133

풀이

문제 풀이의 기본 토대는 백준 11727과 비슷하다.
다만 3XN크기의 벽이라는 점 때문에 달라지는 부분이 있다.
우선 3XN을 2X1, 1X2 타일로 채울 때, 가로길이 N이 홀수면 벽을 다 채우지 못한다.
그래서 짝수인 경우를 살펴보도록 한다.

N=2일 때는 다음과 같이 세 가지 모양의 타일로 벽을 채울 수 있다. DP[2] = 3

N=4일 때는 다음과 같이 DP[2] 각각의 경우에 다시 DP[2] 각각의 경우를 연결할 수 있다. 따라서 DP[4] = DP[4-2] * 3이 된다.

N=6일 때는 우선 벽을 가로 2짜리 타일로 먼저 채우는 경우에는 남는 길이는 N-2(4)의 경우에 가로 길이 2를 만드는 경우 3가지를 곱하면 된다.

그리고 아래와 같이 또 다른 새로운 모양 2개가 추가된다.

N=8일 때는 모양이 이상하지만...다음과 같이 생긴 모양이 2개 추가된다.

결론적으로 N이 짝수일 때 새로운 타일이 2개씩 추가된다.

const readFileSyncPath = require('path').basename(__filename).replace(/js$/, 'txt');
// const readFileSyncPath = '/dev/stdin';
const N = Number(require('fs').readFileSync(readFileSyncPath).toString().trim());
const DP = new Array(N+1).fill(0)

DP[0] = 1
DP[2] = 3

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

console.log(DP[N])