프로그래머스 문제풀이 15

1. 피보나치 수

문제 설명
피보나치 수는 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은 2 이상 100,000 이하인 자연수입니다.


입출력 예
n / return
3 2
5 5


입출력 예 설명
피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.


문제풀이

// 0 , 1 , 1 , 2, 3 , 5, 8, 13
function solution(n) {
   // 피보나치 수의 결과를 저장하는 배열
    // 0번째 인덱스에는 0번째 피보나치 수의 결과를 저장
    // 1번째 인덱스에는 1번째 피보나치 수 결과 저장
    // n번째 인덱스에는 n번째 피보나치 수 결과 저장
    const answer = [0,1];
    for(let i = 2; i <= n; i++){
      // (A + B) % C === ((A % C) + (B % C)) % C
        answer[i] = (answer[i - 1] + answer[i - 2]) % 1234567
        // console.log(i, answer)
    }
    return answer[n]
}

메소드 활용

// 0 , 1 , 1 , 2, 3 , 5, 8, 13
function solution(n) {
    let prev = 0; //0번째 피보나치 수의 결과를 저장
    return Array.from(new Array(n - 1), _ => 1) //반복문이 한번 더 돌고있으므로 n - 1해줘야함.
                .reduce(acc => {
                    // console.log(acc, prev)
                    const sum = (acc + prev)  % 1234567
                    prev = acc // n-2한 값이 계속해서 prev에 저장되야 함
                    return sum;
                }, 1) //첫번째 피보나치 수의 결과를 초기값으로 넣음.   
}

접근방법
1. 세번째 피보나치를 구하려면 1,2번째가 필요함
2. 바로 앞에 있는 피보나치와 그 앞에 있는 피보나치를 구한다면 어떤 피보나치든 상관없이 무한정하게 답을 구해올 수 있다.
3. const answer = [0,1]를 넣어놓고
반복문을 2부터 시작하도록 함
4. answer[i - 1] 해서 앞에 있는 피보나치 수를 구해본다.
5. answer[i - 2] 해서 n-2한 값의 피보나치 수를 뽑아온다.
6. return 할 때 1234567를 나누면 테스트에서 걸리는 이유?
7. 123은 Int로 되어있음.
123123123123123123123123하면
1.23123123123123123e+38 이렇게 나오는데
이것은 지수임!
컴퓨터에서 내주는 결과인데, Int타입은 범위가 지정이 되어있고 그 범위는 2 ** 53 - 1까지가 나타낼 수 있는 범위임.
그 이상을 넘어가면 불안정한 숫자를 내뱉게 되는 것임
Number.isSafeInteger()라는 메서드가 있는데,
안전한 범위에 있다면 true 아니면 false를 반환해준다.
8. 공식이 따로 있음.