[boj] 2133. 타일 채우기 (node.js)

문제

[boj] 2133. 타일 채우기 (node.js)

• 벽의 가로 길이가 주어진다. 이때, 주어진 타일로 채울 수 있는 경우의 수를 구하는 문제

핵심 풀이

• 홀수인 경우 완성할 수 있는 경우가 존재하지 않으므로 0으로 초기화한다.
• 짝수인 경우만 고려한다.
• 해를 구하기 위해 경우의 수를 생각해보면, 타일로 완성시킬 수 있는 최소 단위는 벽의 가로길이가 2일 때이며, (짝수인 경우) 무한정으로 새로운 조합으로 벽을 채울 수 있다!

단계별로 생각하기

for (let i = 3; i <= N; i++) {
  if (i % 2 == 0) {
    dp[i] = dp[i - 2] * 3
    for (let j = 4; j <= i; j += 2) dp[i] += dp[i - j] * 2
  } else dp[i] = 0
}

• 2일 때 채울 수 있는 경우의 수는 총 3이다. 이를 dp배열에 저장하면 dp[2] = 3
• 그 뒤로 짝수인 4, 6, 8, … 을 쭉 생각해볼 수 있는데, 먼저 dp[4]가 될 수 있는 경우는 앞서 구한 2칸을 채울 수 있는 경우의 수인 3을 활용해서 dp[4 - 2] * 3으로 세울 수 있다. 거기다가 4칸을 채울 수 있는 경우의 수 1가지가 새롭게 등장하며, 이를 상하 반전시킬 수 있으므로 최종점화식은 아래와 같다.
• dp[4] = dp[4-2] 3 + dp[4 - 4] 2
• 이 계산을 위해 dp[0] = 1로 초기화해준다.
• 다음으로 6을 생각해보면, 마찬가지로 dp[6] = dp[6 - 2] 3 + dp[6 - 4] 2 이다. 여기서 한 단계 더 생각해보면, 모든 짝수 값이 주어질 때마다 새롭게 전체 크기를 채울 수 있는 모양이 생긴다. 즉, 6칸짜리를 채울 수 있으며 상하반전이 가능하므로 최종 점화식은 dp[6] = dp[6 - 2] 3 + dp[6 - 4] 2 + dp[6 - 6] * 2 이다.
• dp[i] = dp[i - 2] * 3 + dp[i - 4] * 2 + … + dp[0] * 2

전체 풀이

const readline = require("readline")
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
})

const solution = () => {
  const N = input()
  const dp = [1, 0, 3]
  for (let i = 3; i <= N; i++) {
    if (i % 2 == 0) {
      dp[i] = dp[i - 2] * 3
      for (let j = 4; j <= i; j += 2) dp[i] += dp[i - j] * 2
    } else dp[i] = 0
  }
  console.log(dp[N])
}

let line = 0
const input = () => stdin[line++]

let stdin = []
rl.on("line", function (line) {
  stdin.push(line)
}).on("close", function () {
  solution()
  process.exit()
})