백준[JS] > 11726번 타일링

문제

https://www.acmicpc.net/submit/11726/90108724

풀이

2xi 크기의 타일을 채우는 방법은 2x(i-1) 크기의 타일을 채우는 방법의 수와 2x(i-1) 크기의 타일을 채우는 방법의 수를 합산한 값과 같다는 걸 알수 있어야 한다. 만약 dp[i] 가 2 x i 크기의 타일을 채우는 방법의 수라고 하면 점화식은 dp [ i ] = dp [ i-1 ] + dp [ i-2 ] 이다. 이 점화식을 이용하면 문제를 풀 수 있다. dp[1], dp[2], dp[3] 을 직접 구해보면 점화식이 성립함은 쉽게 알 수 있다.

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

const n = +input;
const dp = Array(n + 1).fill(0);

(dp[0] = 0), (dp[1] = 1), (dp[2] = 2);

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

console.log(dp[n] % 10007);