[프로그래머스][Level2][Java] 피보나치 수

문제

 

풀이 코드

public int solution(int n) {
    return fibo(n)%1234567;
}
public int fibo(int n){
    int re = 0;
    int[] arr = new int[n+1];
    if(n==1){
        return arr[n] = 1;
    }else if(n == 2){
        return arr[n] = 1;
    }else{
        return arr[n] = fibo(n-1)+fibo(n-2);
    }
}

처음에는 일반적인 피보나치 문제인 줄 알고 그냥 이렇게 풀었다. 근데...

이렇게 시간초과로 실패를 했다. 그래서 뭐지 하고 생각을 해봤는데 피보나치 수열은 생각해보니 n이 커질수록 숫자가 급격하게 늘어서 int의 범위가 감당할 수 없을 정도로 커지면 오류가 나겠다. 싶어서 Long으로 바꿔야 하나?라는 생각이 들었지만 시간 초과의 문제를 보고 그냥 재귀함수의 문제 같아서 그냥 for문으로 돌렸다.

public long solution(int n) {
        long prev1 = 1L, prev2 = 1L;
        long answer = 1L;
        if(n==1){
            return 1;
        }else if(n==2){
            return 1;
        }else{
            for(int i = 2;i<n;i++){
                answer = prev1 + prev2;
                prev1 = prev2;
                prev2 = answer;    
            }
        }
        return answer%1234567;
    }

이번에는 성공했을 꺼라 믿고 돌렸는데?

또 실패...생각해보니 Long의 인식범위를 피보나치 수열이 벗어나도 오류가 뜨는 거였다...그래서 이리저리 생각하다가

어떤 분께서 (A+B) % C가 ((A%C) + (B%C))%C로 바꿀 수 있다고 하셔서 이거보고 오오 하면서 코드를 다시 바꿨다.

public long solution(int n) {
    long prev1 = 1L, prev2 = 1L;
    long answer = 1L;
    if(n==1){
        return 1;
    }else if(n==2){
        return 1;
    }else{
        for(int i = 2;i<n;i++){
            answer = prev1%1234567 + prev2%1234567;
            prev1 = prev2;
            prev2 = answer;
        }
    }
    return answer%1234567;
}

결과는?

성공~

일반적인 피보나치 수열인 줄 알고 풀었다가 새로운 것을 알게 되어서 좋았다!