피보나치 수

문제

문제 설명
피보나치 수는 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 이하인 자연수입니다.
입출력 예
n	return
3	2
5	5
입출력 예 설명
피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

1차 시도

 function fibonacci(num) {
   if(num <= 1){
     return num;
   }
   return fibonacci(num - 1) + fibonacci(num - 2)
 }


 function solution(n) {

    return fibonacci(n) % 1234567
}

❗️ 우선 문제에 대한 이해를 뒤늦게 알았다.
정상적인 피보나치 수열에서 n번째의 수에서 1234567로 나누어서 남은 나머지의 값을 구하는게 아니었다. 2번째 요소를 1234567로 나누어서 남은 나머지의 값으로 피보나치 수열을 만드는 것이었다.

풀이

function solution(n){
	let answer = []
    for(let i = 0; i <= n; i++){
      if(i === 0) answer.push(0)
      if(i === 1) answer.push(1)
      if(i >= 2){
        let sum = answer[i-1] + answer[i-2]
      	answer.push(sum % 1234567)
      }
    }
  let result = answer[n]
  return result 
}

✅ 그리고 피보나치 수를 구하는 함수를 따로 만들어서 코드를 짜니까 복잡도에서 걸려버렸다. 그래서 다른 분들의 코드를 참고해서 반복문을 통해 피보나치 수열 원리를 구현하였고 fibonacci 배열에 그 값을 넣어주는 것으로 정리를 했다.