[프로그래머스 / Javascript] 피보나치 수

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

✅ 문제 설명

✅ 풀이

// 1차 시도
function solution(n) {
  const arr = [0, 1];

  for (let i = 2; i <= n; i++) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }

  return arr[n] % 1234567;
}

• 해당 문제는 DP문제다.
• F(n) = F(n-1) + F(n-2) 식을 세우기 위해선 현재 숫자의 전 숫자와 전전 숫자를 활용해야하기 때문에 배열을 첫 숫자와 두 번째 숫자를 초기화 한 상태로 시작한다.
• 반복문을 i <= n 조건으로 설정하고 최종적으로 배열[n] 값을 1234567로 나눈 나머지를 return 하는 방식으로 풀이했다. 하지만 오답.
• 찾아보니 피보나치 수열에서 반복문이 계속 진행되다 보면 javascript에서 숫자 자료형이 표현할 수 있는 최대 범위를 넘어가는 경우가 발생할 수도 있다는 것을 알게 되었다.
• 따라서, 배열에 수를 넣어줄 때마다 1234567로 나눈 값을 배열에 넣는다.

// 정답 코드
function solution(n) {
  const arr = [0, 1];

  for (let i = 2; i <= n; i++) {
    arr[i] = (arr[i - 1] + arr[i - 2]) % 1234567;
  }
  return arr[n];
}