[백준] 11727_2 x n 타일링 2 (Javascript)

문제

BOJ_11727_2×n 타일링 2

풀이

이 문제는 dp를 이용해서 해결할 수 있다.
아래 이미지를 보자

위의 이미지를 토대로 점화식을 세워 보면 아래와 같다.

dp[1] = 1, dp[2] = 3 일 때,
dp[i] = dp[i-1] + dp[i-2] * 2

점화식을 토대로 코드를 구현해보면 아래와 같은 코드가 나온다.

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./LJH/input.txt";
let n = Number(fs.readFileSync(filePath).toString());
let dp = {
    1: 1,
    2: 3,
};
for (let i = 3; i <= n; i++) {
    dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 10007;
}

console.log(dp[n]);