프로그래머스 - 피보나치 (Level 2)

1. 메모제이션 사용하지 않고 재귀를 돌리면 시간초과가 발생

2. 메모제이션을 사용하니 7번 테케부터 오류가 발생

3. 원인을 모르겠어 검색해 보니 

->

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

예를 들어
100,000번째 피보나치 수는 자릿수가 20,000을 넘어가며, 

이는 64비트 정수(ex. long) 범위를 넘어 오버플로우가 발생합니다.

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

 

라고 하여 수정한 결과 성공!

 

import java.util.*;
class Solution {
    public long Fibo(int n,long[] memo){
        if(memo[n]>-1)
            return memo[n]%1234567;
        else{
            if(n<2)
                memo[n]=n;
            else
                memo[n]=Fibo(n-1,memo)+Fibo(n-2,memo);
            
            return memo[n]%1234567;
        }   
    }
    public int solution(int n) {
        long[] memo=new long[n+1];
        Arrays.fill(memo,-1);
        long answer=Fibo(n,memo);
       
        return (int) answer;
    }
}