[백준] 1904. 01타일 (자바스크립트/javascript/js/동적계획법/다이나믹프로그래밍/동적프로그래밍)

 

문제를 풀기 위한 아이디어

다이나믹 프로그래밍 유형은 점화식을 세우는 것이 가장 중요하다.

이 문제의 점화식은 타일의 개수가 N개일 때 만들 수 있는 N자리수 이진수의 모든 개수를 T(n)이라 하면,

T(n) = T(n-2) + T(n-1)이다.

다이나믹 프로그래밍을 푸는 방법에는 Top-down 방식과 Bottom-up 방식이 있는데, 처음에 이문제를 Top-down 방식으로 푸니까 stack이 계속 초과되었다고 나와서 Bottom-up 방식으로 반복문으로 풀었다.

 

 

내가 작성한 코드 (자바스크립트)

function solution(N) {
  const memo = new Array();
  memo[1] = 1;
  memo[2] = 2;
  for (let i = 3; i <= N; i++) {
    memo[i] = (memo[i - 2] + memo[i - 1]) % 15746;
  }
  console.log(memo[N]);
}

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let input;
rl.on("line", function (line) {
  input = line;
  solution(Number(input));
  rl.close();
}).on("close", function () {
  process.exit();
});