문제링크
https://programmers.co.kr/learn/courses/30/lessons/12945
문제 설명
피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.
예를들어
- F(2) = F(0) + F(1) = 0 + 1 = 1
- F(3) = F(1) + F(2) = 1 + 1 = 2
- F(4) = F(2) + F(3) = 1 + 2 = 3
- F(5) = F(3) + F(4) = 2 + 3 = 5
와 같이 이어집니다.2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.
제한 사항
- n은 2 이상 100,000 이하인 자연수입니다.
입출력 예
문제풀이
시도1. 재귀로 풀려고 했으나 시간초과가 떴다.
시도2. 배열에 값들을 차례로 넣고 이전값과 그 이전 값을 더해 정답을 출력한다.
- 근데 제출해보니 7번부터 오류가 발생했다... 질문하기에서 글들을 확인해보니 숫자가 너무 커져서 그렇다고 한다. 그래서 마지막 return에 1234567로 나눈 나머지를 리턴해주었는데도 해결이 되지 않았다. 알고보니 push할때도 1234567로 나눈 나머지를 푸시해주었어야 했다.
코드
function solution(n) {
return fibo(n);
}
function fibo(n){
let num = 2;
let arr = [0,1];
while(num != n){
let sum = 0;
for(let i=num-2; i<num; i++) sum += arr[i];
// 이 부분 수정
arr.push(sum%1234567);
num++;
}
return (arr[n-1] + arr[n-2]) % 1234567;
}다른사람 코드
function solution(n) {
var result = [0 , 1];
while ( result.length !== n + 1) {
var fibonacci = (result[result.length - 2] + result[result.length - 1]) % 1234567
result.push(fibonacci);
}
return result[n];
}비슷하긴 한데 변수를 따로 두지 않고 result.length로 제어할 수도 있다.
TIL
- 재귀는 while보다 시간소요가 더 된다.
