시간 초과, 런타임 오류

function fibonacci (n){
    if(n === 0){
        return 0;
    }
    
    if(n === 1){
        return 1;
    }
    
    return fibonacci(n - 1) + fibonacci(n - 2);
}

function solution(n) {    
    return fibonacci(n) % 1234567;
}

재귀를 사용했다. 그러나 런타임 오류까지 발생했다.
알아보니 숫자가 너무 커서 int 타입으로는 해결이 안되는 모양이다.
그러면...BigInt를 써야하는걸까?

맞긴한데...좀 더 찾아보니 문제가 이상하다는 말이 있었다.

적혀있는 문제대로라면...
n번째 피보나치 수를 1234567로 나눈 것을 반환하라는 것 같은데,
실제로는 피보나치 수를 구할 때마다 1234567로 나눈 것 중에서 n번째 수를 반환하는 것이다.

이해가 안되서 다른 분 풀이를 봤다.

다른 분 풀이

function solution(n) {
    let answer = 0;
    let f0 = 0
    let f1 = 1;
    
    for(let i = 2; i <= n; i++){
        answer = (f0 + f1) % 1234567;
        f0 = f1;
        f1 = answer;
    }
    
    return answer;
}

피보나치 수 answer를 구하기 위해 f0,f1을 더한 것을 1234567로 나누는 것을 볼 수 있다.
즉, 따라서 n번 피보나치 수는 해당 피보나치 수를 1234567로 나눈 나머지를 가지게 되며,
다음 피보나치 수를 구하기 위해 f0에는 f1을, f1에는 answer를 넣어준다.
n번 반복한 뒤 answer를 반환한다.

참고 자료

developerm님 블로그