[실버3] 백준 11727 - 2×n 타일링 2

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

Solution

코드

const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const N = +require('fs').readFileSync(path).toString().trim();

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

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

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

console.log(dp[N]);

이전과 같은 나머지 연산

결과를 출력하는 부분에서 % 10007을 하면 틀렸습니다가 뜬다. Python을 이용해서 문제를 풀 때에는 이상이 없었는데, JavaScript를 사용하면 발생하는 문제였다,,,

Python의 경우 정수(integer)의 크기에 제한이 없기 때문에 대부분의 경우 오버플로우 문제를 걱정할 필요가 없습니다. 따라서 2번 코드처럼 결과값을 모두 계산한 후에 모듈로 연산을 하는 것이 정답이 될 수 있습니다. 그러나 JavaScript의 경우 숫자 처리가 부동소수점(float)과 정수(integer)로 구분되며, 일반적으로 숫자가 2^53보다 크거나 작을 때 정수로 표현되고 그 이상일 때는 부동소수점으로 처리됩니다. 따라서 매우 큰 값의 경우 오버플로우 문제가 발생할 수 있습니다.

혹시나 했는데 역시나 오버플로우 때문이었군