백준 2748 : 피보나치 수2

💡기본 정보

유형
: DP
풀이 날짜
: 2025년 01월 28일 
풀이방법 한줄 요약
: bottop-up형식으로 점화식 세워서 구현

 

💡문제에서 구해야 할 것

피보나치 수는 0과 1로 시작함 . 0번째 피보나치 수는 0이고 1번째 피보나치 수는 1임 그 다음 2번째부터는 바로 앞 두 피보나치 수의 합
이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2) 가 됨
n이 주어졌을 때 n번째 피보나치 수를 구하는 프로그램을 작성하시오
- 입력 : 첫째 줄에 n이 주어짐 . n은 90보다 작거나 같은 자연수
- 출력 : 첫째 줄에 n번째 피보나치 수를 출력

💡알고리즘 설계

- Bottom-up 방식으로 반복문 구현
- F0 = 0

   F1 = 1

   F2 = F1 + F0 = 1
   Fn = Fn-1+Fn-2 

 

💡CODE

const fs = require("fs");
const N = Number(fs.readFileSync(0,"utf8").toString().trim());
const F = new Array(N+1).fill(0n);
function fibonacci(){
    F[0]=0n;
    F[1]=1n;
    for(let i = 2; i<=N;i++ ){
        F[i]=F[i-1]+F[i-2];
    }
    return F[N];
}
console.log(fibonacci().toString());

 

💡시간복잡도

 

💡 틀린 이유 & 틀린 부분 수정

const F = new Array(N+1).fill(0n);

-> 크기가 커질 수 있어서 BigInt로 처리해야함

 

💡 다른 풀이 or 기억할정보

BigInt로 처리시 출력할 때 .toString()으로 출력해야함