자바 [Programmers] 2단계 - 피보나치 수

 

틀린 코드

class Solution {
    public int solution(int n) {
        int answer = fi(n);
        
        return answer % 1234567;
    }
    
    private int fi(int n){
        if(n == 0){
            return 0;
        }else if(n == 1){
            return 1;
        }
        return fi(n-2) + fi(n-1);
    }
}

 

위 코드 대로 했더니 시간 초과가 났다.

단순 피보나치 구현 문제인 줄 알았는데 시간 초과가 났다는건 피보나치 구현을 dynamic programming을 써야된다는 것을 파악했다.

 

수정 코드

class Solution {
    public int solution(int n) {
        int[] dp = new int[n+1];
        
        dp[0] = 0;
        dp[1] = 1;
        
        for(int i=2; i<=n; i++){
            dp[i] = (dp[i-2] + dp[i-1]) % 1234567;
        }
        
        return dp[n];
    }
}