99클럽 코테 스터디 2일차 TIL - 피보나치 비스무리한 수열

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

첫 번째 시도

• f(n) = f(n-1) + f(n-3)이며 f(1) = f(2) = f(3) = 1인 수열이라는 조건에 맞춰 작성했으나 실패

const fs = require("fs")
const n = Number(fs.readFileSync("/dev/stdin").toString().trim())

const arr = []
arr[1] = 1
arr[2] = 1
arr[3] = 1

for (let i = 4; i <= n; i++) {
  arr[i] = arr[i - 1] + arr[i - 3]
}

console.log(arr[n])

실패한 이유

• JavaScript에서 Number 타입이 안전하게 표현할 수 있는 최대 정수는 2^53 - 1 (≈ 9,007,199,254,740,991) 이고, 이를 초과하는 정수 연산에서는 BigInt가 필요함
• f(53)부터 2^53 - 1을 초과하기 시작하므로 BigInt를 사용해야 안전하게 계산할 수 있음

최종 코드

const fs = require("fs")
const n = Number(fs.readFileSync("/dev/stdin").toString().trim())

const arr = [0, 1, 1, 1].map(BigInt)

for (let i = 4; i <= n; i++) {
  arr[i] = arr[i - 1] + arr[i - 3]
}

console.log(arr[n].toString()) // BigInt는 뒤에 n이 붙기 때문에 toString 필요