피보나치 수→ 오버플로우 극복방법: %★★★

나의 풀이 

class Solution {
   public int solution(int n) {
        int answer = 0;
        int[] fibo = new int[n + 1];
        fibo[0]=0;
        fibo[1]=1;
        System.out.println("fibo.length = " + fibo.length);
        for (int i = 2; i < fibo.length; i++) {

            int sum=fibo[i-1]+fibo[i-2];
            fibo[i]=sum % 1234567;
            }
        return fibo[fibo.length-1] % 1234567;

        }
}

 

🚨이런 문제가 있어요
n이 매우 큰 경우 n번째 피보나치 수는 언어가 표현할 수 있는 자료형의 범위를 넘어가, 오버플로우가 납니다.

예를 들어

47번째 피보나치 수는 2,971,215,073이고, 이 수는 32비트 정수(ex. int) 범위를 넘어 오버플로우가 발생합니다.
100,000번째 피보나치 수는 자릿수가 20,000을 넘어가며, 이는 64비트 정수(ex. long) 범위를 넘어 오버플로우가 발생합니다.

💡그럼 코드를 어떻게 바꾸면 좋나요?
모든 단계에서 % 연산을 사용하여, 모든 연산에서 오버플로우가 일어나지 않게 만들어 주세요.



▶오버플로우 고려하기 전 : fibo[i] =fibo[i-1]+fibo[i-2];


▶오버플로우 고려 후  int sum=fibo[i-1]+fibo[i-2];
                                    fibo[i] =sum % 123457