[node.js] 2xn 타일링2 ( 백준 11727번 )

const readline = require("readline");

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

rl.on("line", (line) => {
    main(line);
    rl.close();
}).on("close", () => {
    process.exit();
});

const main = (line) => {
    line = Number(line);
    const DP = new Array(line + 1).fill(0);
    DP[1] = 1;
    DP[2] = 3;

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

앞전 문제랑 같다. 다만 경우의 수가 마지막에 세로를 놓는가, 가로를 놓는가, 정사각형을 놓는가 3가지의 경우의 수다.
이전 문제를 먼저 풀고 다시 이것을 보면 분명히 이해가 될 것이다.
결국, i번째는 n-1번째와 n-2번째, 그리고 n-2번째의 합과 같을 수 밖에 없다.