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

https://programmers.co.kr/learn/courses/30/lessons/12945

코딩테스트 연습 - 피보나치 수

2021-07-30

---

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

#문제풀이

메모이제이션을 이용하여 풀었다. O(N)

---

재미로 다른 방법으로 풀어본다면,

 

다음과 같이 단순 재귀로 풀면

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

 O(2^N)으로 7번 테스트부터 시간초과가 난다.

 

 

Bottom-up 방식으로 풀면,

class Solution {
    public int solution(int n) {
        int fn1 = 1;
        int fn2 = 0; 
    
        int answer = 0;
        for(int i = 2; i <= n; i++) {
            answer = (fn1 % 1234567) + (fn2 % 1234567);
            fn2 = fn1;
            fn1 = answer;
        }
        
        return answer % 1234567;
    }
}

O(N)이다. 귀찮아서 배열은 만들지 않고, fn1, fn2 변수에다가 값을 저장했다.