연습장/백준(BOJ) 문제풀이
[백준 2748 - Node.js] 피보나치 수 2
Tesseractjh
2022. 3. 19. 15:56
문제 링크
https://www.acmicpc.net/problem/2748
2748번: 피보나치 수 2
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가
www.acmicpc.net
풀이
const n = +require('fs').readFileSync('/dev/stdin').toString().trim();
const dp = Array(n + 1).fill(BigInt(0));
dp[1] = BigInt(1);
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
console.log(dp[n].toString());피보나치 수 문제와 풀이는 동일하나, 주어지는 n의 최댓값의 차이로 인해 자바스크립트에서 나타낼 수 있는 가장 안전한 최대 크기의 정수인 Number.MAX_SAFE_INTEGER(2^53 - 1)보다 큰 수가 dp에 저장되면서 정확하지 않은 수가 입력될 수 있다.
따라서, BigInt를 사용한 연산을 통해 정확한 값을 얻어내야 한다.
마지막에 출력할 때 BigInt의 리터럴의 마지막에 알파벳 n이 붙기 때문에, 문자열로 변환하여 출력하였다.