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

 

이 문제는 문제를 이해하는데 시간이 걸렸다. 

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수를 말하는데 

0번째 피보나치 수가 0, 첫번째 피보나치 수가 1인건 정해져 있고 두번째 피보나치 수는 앞에 두개를 더한 1이 된다는 말이다.

예를 들어보면 0 1 1 2 3 5 8 13 과 같이 n-1 번째 수와  n-2번째 수가 더해져 n번째 수가 되는 법칙이 성립된다고 생각하면 된다. 

그런데 문제에서 생뚱맞게 1234567 로 나누라고 해서 이게 뭐지 했는데 피보나치 수 44만 해도 2,971,215,073로 int의 값을 훨씬 넘은 수라 int 내에서 해결하기 위한 문제 의도라고 한다. 

 

function getFibonacci(n) {
    let fibonacciArr = [0, 1, 1];
    for(let i = 3; i <= n; i++ ) {
        fibonacciArr[i] = (fibonacciArr[i-1] + fibonacciArr[i-2]) % 1234567;
    } 
    console.log(fibonacciArr)
    return fibonacciArr[n]
}

function solution(n) {
    const answer = getFibonacci(n)
    return answer
}

 

코드는 정말 설명 그대로 적으면 돼서 어려울게 없는데 문제를 이해하는데 시간을 많이 쏟은 것 같다. 

시간 복잡도 O(n) 걸린다.