피보나치 수 2 - 2748

문제 링크

문제 설명

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

이 문제를 풀었는데 출력은 맞게 나오는데 자꾸 문제 해결이 되지 않는다 .. !
결국 구글링을 하였고 LHOIKTN님의 풀이를 보았고 BigInt을 발견했다.

BigInt

BigInt는 자바스크립트에서 정수형 데이터의 크기 제한을 초과하는 큰 숫자를 처리하기 위한 자료형이다. 일반적으로 자바스크립트 숫자 타입인 Number는 64비트 부동소수점 숫자를 사용하며, 이는 안전하게 표현할 수 있는 정수의 최대 범위가 -2^53에서 2^53-1이다. 이 범위를 넘는 숫자를 처리해야 할 경우 BigInt를 사용한다.

풀이

const fs = require('fs');
const X = +fs.readFileSync("./dev/stdin").toString().trim()

let dp = new Array(91).fill(null);
dp[0] = 0;
dp[1] = 1;

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