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

문제

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

 

풀이

문제의 핵심은 다음과 같은 점화식을 구하는 것이다.

 

dp[i] = dp[i-1] + dp[i-1]*2 

 

dp[i] 는 2xI 직사각형의 타일을 채우는 방법이다. 

 

해당 점화식만 도출하면 쉽게 풀 수 있다.

 

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim();

let N = Number(input);

let dp = Array(N + 1).fill(0);

dp[1] = 1;
dp[2] = 3;

for (let i = 3; i <= N; ++i) {
    dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 10007;
}

console.log(dp[N]);