[백준] 2748: 피보나치 수 2 - JS (재귀, DP)

 

  목 차

• 문제
• 접근 방식
• 풀이

 

---

 

  문제

 

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

 

 

  접근 방식

 

이 문제는 대표적인 DP 문제이다. 그냥 재귀함수를 통해서 문제를 푼다면 시간이 초과되어 실패할 것이다.

>> DP란?

 

백준에서 입력은 첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다. 라고 되어있다.

자바스크립트에서 표현할 수 있는 가장 큰 값을 넘어서는 값이다.

그래서 이 문제를 해결하기 위해서는 BigInt를 사용하여 문제를 해결해야 한다.

 

그리고 정확한 표현을 위해서 마지막에는 .toSting()메서드를 사용하여 출력해 준다.

 

 

  풀이

 

let dp = [BigInt(0), BigInt(1)]  // BigInt

function fibonacci(n) {
  if (n < 0) { throw new Error ('정수 넣으세요.')}
  if (dp[n] !== undefined){
    return dp[n];
  };
  console.log(`Calculating fibonacci(${n})`);  // DP가 잘 적용되었는지 확인하는 console.log 메서드
  dp[n] = fibonacci(n - 1) + fibonacci(n - 2);
  return dp[n];
};

console.log(fibonacci(90).toString());  // 정확한 표현을 위해 toSting 메서드 사용