[백준 11727/javascript] 2Xn 타일링 2

다이나믹 프로그래밍 문제

n = 1 일때부터 경우의 수를 구해서 규칙을 찾아보면

n 의 경우의 수 = (n - 1 의 경우의 수) + (n - 2 의 경우의 수) * 2   의 규칙을 갖는 것을 알 수 있다

나머지는 매 경우마다 구해주고

배열에 bottom up 방식으로 채워나가 완성해주자

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

let input = [];

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

readline.on("line", (line) => {
  input.push(line);
});

readline.on("close", () => {
  solution(input);
  process.exit();
});

const solution = (inp) => {
  let n = Number(inp[0]);
  let arr = Array(1004).fill(0);
  arr[1] = 1;
  arr[2] = 3;

  for (let i = 3; i <= 1000; i++) {
    arr[i] = (arr[i - 1] + arr[i - 2] * 2) % 10007;
  }
  console.log(arr[n]);
};