[JS] 2×n 타일링 2 - 백준11727

문제

시간복잡도

O(n)

해결방법

dp[i] 는 dp[i-1]에서 세로블럭을 붙인 것과 dp[i-2]에서 2x2 블럭 또는 가로블럭 두개를 붙인 모양들이다.

dp[i-2]는 두가지 모양을 붙일 수 있으니 dp[i-2]*2만큼 만들 수 있다.

 

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

 

참고 - 최대 정수값

 

자바 스크립에서 안전한 최대 정수값은  2^53 - 1 이다.

다음과 같이 이 값을 넘어가면 같은 숫자로 인식하여 정확한 값이 나오지 않는다. 

이 문제에서는 10007로 나눈 나머지를 구하라고 했으니 먼저 나눠서 저장해주자.

console.log에서 %10007을 하면 런타임 에러가 난다.

const x = Number.MAX_SAFE_INTEGER + 1;
const y = Number.MAX_SAFE_INTEGER + 2;

console.log(Number.MAX_SAFE_INTEGER);
// Expected output: 9007199254740991

console.log(x);
// Expected output: 9007199254740992

console.log(x === y);
// Expected output: true

 

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./example.txt";
let input = fs.readFileSync(filePath).toString();
input = parseInt(input);
dp = [0, 1, 3, 5];

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

console.log(dp[input]);