[JavaSrcipt] Baekjoon - 2747 : 피보나치 수

문제

피보나치 수는 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은 45보다 작거나 같은 자연수이다.

출력

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

예제입력	예제출력
10	55

 

⭕ 풀이

const input=Number(require('fs').readFileSync('/dev/stdin').toString());
let arr=[0,1];
let temp;
for(let i=1;i<input;i++){
    
    temp=arr[1]
    arr[1]=arr[0]+arr[1];
    arr[0]=temp;
    
}

console.log(input==0?0:arr[1])


///////////////////////////////////

const input=require('fs').readFileSync('/dev/stdin').toString();
let n=+input;
let arr=[0,1];
for(let i=2;i<=n;i++){
    
    arr[i]=arr[i-1]+arr[i-2];
    
}
console.log(arr[n])

이전 피보나치문제를 복습할겸 비슷한문제를 찾아

재귀함수를 사용해 풀이해보았는데 이번에는 문제입력값이 이전문제보다 큰경우가있어

시간초과판정을 받는다.

 

그래서 재귀를 사용하지않고 풀어보았더니 정답처리되었다.

 

문제에따라 재귀함수를 사용하는것이 나을때가있고

단순 반복문처리하는게 나을때가 있다고 쓰기나름이라던데

이런경우는 반복문이 더 나은경우같다.

 

단계별로 풀어나가고있었는데

재귀함수단계에 들어오면서 꽉막힌기분이다.

사실 오늘 하노이의탑문제를 보고 또 보고 다른분들의 풀이까지 봤는데도

아직 이해가 완벽히되지않아 다른문제로 대체했다.

머릿속에서 돌아가지않아 써가며 풀어봤는데도 아직 이해가 부족하다..

 

재귀가 진입장벽이라는 말들이 가끔 있던데 체감중이다

 

 

-출처

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