[프로그래머스] 피보나치 수 - JS

피보나치 수

❓ 문제설명

피보나치 수는 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

💡 풀이

function solution(n) {
  // 피보나치 배열
  const map = new Array(n + 1).fill(-1)
  
  // 0부터 n 까지 피보나치수를 차례로 계산
  for (i=0; i<=n; i++) {
    if (i < 2) map[i] = i
    else map[i] = (map[i-2] + map[i-1]) % 1234567
  }

  return map[n]
}

📝 해설

피보나치 수는 재귀로 풀 수도 있지만 n이 100,000 보다 작기 때문에 배열로 처리하고 생각하였다. 일반적인 피보나치 수 알고리즘과 동일하지만 1234567 로 나눈 나머지를 리턴해야 하는 문제가 있는데 덧셈에 대해서 ( A + B ) % 1234567 = A % 1234567 + B % 1234567 이 성립하기 때문에 F(n) = (F(n-2) + F(n-1)) % 1234567 으로 처리하였다.