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

# 문제 원문

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

# 문제 풀이

간단한 문제이지만, 자료형 범위로 인한 데이터 오류 + 콜스택 제한으로 인한 런타임 오류가 나온다. 피보나치수 자체는 재귀 함수를 연습할때 접하는 문제인데 재귀함수로 풀 경우 에러가 나온다는게 나름 노린게 아닐까 생각이든다.

 

# 솔루션 플로우

1. 입력 받은 n까지 3에서 부터 시작해서 반복한다.

2. 피보나치 수의 특징인 fibo(int) = fibo(int - 1) + fibo(int - 3)을 통해서 피보나치 수를 구한다.

3. 그렇게 구해진 fibo(int)을 1234567로 나눈 나머지를 저장한다.(자료형 범위 때문)

4. 위의 과정을 입력 받은 n까지 반복해서 result를 구한다.

5. 얻어진 result를 반환한다.

1. 반복문을 활용한 풀이

function solution(n) {
    const fiboCache = {
        0: 0,
        1: 1,
        2: 1
    };

    for (let int = 3; int <= n; int++) {
        fiboCache[int] = (fiboCache[int - 1] + fiboCache[int - 2]) % 1234567;
    }

    return fiboCache[n];
}