[백준 11726번] 2 x n 타일링 - 자바스크립트(nodejs)

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

11726번: 2×n 타일링

const fs = require('fs');
const input = +fs.readFileSync('dev/stdin').toString().trim();

const obj = {
  1: 1,
  2: 1,
};

for (let i = 3; i <= input; i++) {
  obj[i] = (obj[i - 1] + obj[i - 2]) % 10007;
}

console.log(obj[input]);

타일 수는 피보나치로도 풀 수 있다. 그러나 해당 문제에선 입력값이 너무 크기 때문에 

피보나치로 구현하면 시간초과가 기본적으로 뜬다.

 

2 x n 타일링 문제는 점화식이 구현된다.

DP[i] = DP[i-1] + DP[i-2] 이다.

 

따라서 초기값만 지정해주고, 그냥 점화식으로 구현해주면 된다.