[알고리즘] 피보나치 수

문제) 피보나치 수는 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을 완성해 주세요.

• java

import java.util.ArrayList;
class Solution {
    public static int solution(int n) {
        ArrayList<Integer> list=new ArrayList<Integer>();
        
        list.add(0);
        list.add(1);
        
        for(int i=2;i<n+1;i++) {
        	list.add(i,(list.get(i-1)+list.get(i-2))%1234567);
        }
        
        return list.get(n);
    }
}

• javascript

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

이 문제에서의 문제 점은 피보나치 수를 구하는 코드는 어렵지 않지만 n이 증가하다보면 int의 범위를 넘아가는 피보나치 수가 되어서 정상적으로 계산이 되지 않는다는 것이다. 따라서 1234567로 나눈 나머지를 구하는 것에 초점을 두고 애초에 배열에 넣는 값을 피보나치 수를 넣는 것이 아니라 피보나치 수를 1234567로 나눈 나머지를 넣는다고 생각하면 된다. (A+B)%C는 A%C+B%C와 같다는 점을 이용하여서 위와 같이 풀면 된다.