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

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12945?itm_content=course14743 

프로그래머스

2. 설명

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수를 만들어야 한다.

0번째 수와 1번째 수는 각각 0,1 고정이므로 fi 배열에 넣어준다.피보나치 수열은 i-1 과 i-2, 즉 이전과 그 이전의 수를 더한 값이 i값이 되므로, 배열에 i = 2부터 입력받은 n까지 (fi [i-1]+fi [i-2])을 push 해준다.

이 문제에서 주의해야할 점은, 자료형의 범위를 고려하여 변수에 값을 저장해야 한다는 것이다.

int는 -2,147,483,648 ~ 2,147,483,647까지의 값만을 표현할 수 있다고 한다. 만약 answer = fi[n] & 1234567을 해준다면, int 자료형의 범위를 넘어가는 수가 answer에 저장되기 때문에 원하는 값이 아닌 이상한 숫자가 나온다.

해당 링크에 자세한 설명이 있다!

https://school.programmers.co.kr/questions/11991

프로그래머스

자료형의 크기에 제한이 있는 언어를 쓸 경우, 매번 계산 결과에 1234567으로 나눈 나머지를 대신 넣어야 한다.이를 활용하여 (fi[i-1]+fi[i-2])% 1234567 배열에 피보나치 수가 아닌 결과 값을 1234567로 나눈 수를 push 해주면 자료형의 범위를 넘어가지 않고 fi(n) 값에 내가 원하는 수가 저장되게 된다.

3. 코드

function solution(n) {
    let fi = [0,1];
    for (let i = 2; i <= n ;i++){
        fi.push((fi[i-1]+fi[i-2])% 1234567);
    }
    return fi[n];
}

타임아웃 + 런타임 에러 코드

function solution(n) {
    if(n <= 1) return n;
    
    return (solution(n-1)% 1234567 + solution(n-2)% 1234567)% 1234567;
}