[백준] 2xn 타일링 2 | 자바스크립트 JS | 다이나믹 프로그래밍 DP | S3

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

풀이 과정

DP에 사용할 점화식을 찾기 위해 직접 그려가면서 경우의 수를 계산해본다

N이 홀수/짝수인지에 따라 달라지는 점화식 도출

 

제출 코드

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

const solution = (N) => {
  const dp = new Array(N + 1).fill(1);
  for (let i = 1; i < N + 1; i++) {
    i % 2 === 1 ? dp[i] = (dp[i - 1] * 2 - 1) % 10007 : dp[i] = (dp[i - 1] * 2 + 1) % 10007;
  }
  console.log(dp[N]);
};

readline
  .on("line", function (line) {
    solution(+line);
    readline.close();
  })
  .on("close", function () {
    process.exit();
  });

 

문제 링크

11727번: 2×n 타일링 2