[JAVA] 피보나치 수

문제 설명

피보나치 수는 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, ... 와 같이 이어집니다.

풀이 과정

단순히 n번째의 피보나치 수열값이 나올때 까지 반복하는 방식으로 진행하지만

차이점이 있다면 계산과정에서 미리 1234567의 나머지를 구하는 식이다

나머지는 결국 축적되는 것이며 계산 중에 나머지를 구해도 변함이 없으며

만약 나머지로 구하지 않는다면 overflow되어 int범위를 넘어선 숫자에서 올바른 값을 얻지 못하기 때문이다

풀이

class Solution {
    public int solution(int n) {
        // 피보나치 수열
        int num = 1;
        int prve = 0;
        int fron = 1;
        while(true){
            num++;
            int temp = prve+fron;
            // overflow로 미리 나머지로 계산
            prve = fron%1234567;
            fron = temp%1234567;
            if(n==num){
                break;
            }
        }
        return fron;
    }
}