피보나치 수

문제

문제 설명

피보나치 수는 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은 1이상, 100000이하인 자연수입니다.

입출력 예

n	return
3	2
5	5

입출력 예 설명

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

 

접근 및 풀이

재귀는 깊이가 너무 깊어지므로 반복문으로 접근했다. 그런데 다루는 수가 워낙 커져서 정상적으로 피보나치수를 구하고 1234567을 나누면 Infinity에 나누기가 되어 NaN이 결과로 출력된다. 값으로 저장하기 전에 미리 나누어 나머지 값을 저장함으로써 해결했다.

코드

function solution(n) {
  let a = 0;
  let b = 1
  let c = null;
  for (let i = 2; i <= n; i++) {
      c = (a + b) % 1234567;
      [a,b] = [b,c];
  }
  return c;
}

출처

https://programmers.co.kr/learn/courses/30/lessons/12945