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

문제

시간복잡도 

O(n)

 

해결 방법

위 그림처럼 dp[i]는 dp[i-1]에 세로 블럭을 하나 더한 것과 dp[i-2]에 가로 블럭을 두개 더한 값이다.

dp[i]=dp[i-1]+dp[i-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, 2, 3, 5];

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

console.log(dp[input]);

 

 

출처: (최대 정수값) https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Number/MAX_SAFE_INTEGER