[JS] 백준 2748번 피보나치 수 2

 

출처

백준 온라인 저지

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

2748번: 피보나치 수 2

 

문제

피보나치 수는 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번째 피보나치 수를 구하는 프로그램을 작성하시오.

풀이

1003번의 피보나치 함수 문제를 해결했다면 이 문제도 쉽게 해결할 수 있을 것 같았지만, 생각하지 못했던 문제가 존재했습니다.

 

90 피보나치 수는 '2,880,067,194,370,816,000'의 엄청 큰 수입니다.

하지만 javascript에 존재하는 한계점으로 인해 정확한 수를 표시할 수 없었습니다.

 

그러므로 '2,880,067,194,370,816,000' 범위를 넘은 값을 나타낼 수 있는 객체가 필요하게 됩니다.

그리고 그 해답은 ' BigInt ' 객체였습니다.

 

DP의 값들을 BigInt 객체 형식으로 바꾸어 피보나치 수를 계산해주고 마지막 출력 단계에서 BigInt의 값을 진수로 표현시켜주는 내장 toString 메서드를 사용하여 반환시켜줍니다. 

 

코드

const n = require('fs').readFileSync('/dev/stdin').toString() * 1;

const DP = [0, 1];

for (let i = 1; i < n; i++) {
    DP[i+1] = BigInt(DP[i]) + BigInt(DP[i-1]);
}

console.log(DP[n].toString());

 

다른 코드

1003번 문제에서 사용했던 이전 값만을 계속 바꿔주어 누적시키는 방법을 사용했고 이 방법 또한 BigInt 객체를 사용하였습니다.

 

const len = require('fs').readFileSync('/dev/stdin').toString() * 1;

let prevN = 1, n = 0;

for (let i = 0; i < len; i++) {
    const tmpPrevN = BigInt(n);

    n = tmpPrevN + BigInt(prevN);

    prevN = tmpPrevN;
}

console.log(n.toString());

 

참고 사이트

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/BigInt

BigInt - JavaScript | MDN

 

https://gurtn.tistory.com/83

[JS] 아주 큰 숫자 한계 처리