Bigint

피보나치 수를 구하는 문제인데 나는 왜 계속 틀리는가

아래 문제는 n 번째 피보나치 수를 구하는 단순한 문제입니다.
그러나 저는 두 번이나 제출에서 틀렸습니다를 보게 되었습니다.

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

const input =
  require('fs')
    .readFileSync(process.platform === 'linux' ? 'dev/stdin' : 'test/test.txt')
    .toString()
    .trim() * 1

const dp = Array.from({ length: input + 1 }, (_, i) => i)

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

console.log(dp[input])

위 코드는 점화식도 올바르고 답에 해당하는 인덱스도 올바르게 작성했지만 채점을 통과하지 못합니다. 그 이유는 n의 크기가 90이 되었을 때 피보나치 수가 매우 커진다는 것이었습니다.

자바스크립트의 Number타입이 안정적으로 출력할 수 있는 최대치의 정수인 2^53-1보다 큰 수를 배열에 저장하려 했고, 이로 인해 제대로 피보나치 수가 계산이 안되었던 것이지요.

const input =
  require('fs')
    .readFileSync(process.platform === 'linux' ? 'dev/stdin' : 'test/test.txt')
    .toString()
    .trim() * 1

const dp = Array.from({ length: input + 1 }, (_, i) => i)

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

console.log(dp[input].toString())

그래서 BigInt 내장객체를 통해 2^53-1보다 더 큰 정수들을 연산할 수 있도록 코드를 수정했습니다.

BigInt끼리의 연산은 BigInt를 반환하고, BigInt가 실제로 어떤 정수인지는 .toString()을 통해 문자열로 변환하여 출력했습니다.

교훈

자바스크립트에서 큰 정수의 연산을 수행할 때는 주의하자! 그리고 BigInt를 활용하자!