[프로그래머스,Level 2] 피보나치 수 (JAVA 구현)

- 첫 풀이 및 정답풀이

  재귀를 통해 간단하게 풀 수 있는 대표적인 문제인 피보나치 수를 구하는 문제이다. 단, 문제에서 피보나치 수를 1234567로 나눈 나머지를 원하며, n의 범위가 100000 이하 이므로 dp를 활용해 풀어야 한다. 

 

  dp를 활용해 중복되는 계산과정을 반복하지 않고, 한 번만 계산을 수행해 해당 값을 저장해 둔 뒤 참조만 하는 형식으로 진행하면 된다. 과정은 아래와 같다.

 

  1. 피보나치 수 0은 0, 1은 1이므로 재귀메소드로 들어온 값이 0이면 0, 1이면 1을 반환한다.

  2. 2 부터는 초기의 dp 배열에 값이 존재하지 않으므로 dp [2] = ( fibonacci(n-1) + fibonacci(n-2) ) % 1234567;을 수행한다. 

  3. 3은 fibonacci(2)+fibonacci(1) 이므로 각각 dp [2], 1을 더해 dp [3]에 저장한다. 

 

  위 과정을 반복하면 원하는 자연수의 피보나치 수를 구할 수 있다.

 

class Solution {
    // 1. 피보나치 수를 참조할 메모이제이션.
    static int dp[] = new int[100001];
    
    // 2. 피보나치 메소드
    public static int fibonacci(int n){
        // 3. 0인 경우는 0을 반환.
        if(n == 0) return 0;
        // 4. 1인 경우는 1을 반환.
        if(n == 1) return 1;
        
        // 5. dp[n]에 아직 값이 없다면, 아래의 식을 수행.
        if(dp[n] == 0)
            dp[n] = (fibonacci(n-1)+ fibonacci(n-2)) % 1234567;
        
        // 6. 값이 있다면 dp의 값을 참조해 바로 반환.
        return dp[n];
    }
    
    public int solution(int n) {
        int answer = 0;
        
        // 7. 피보나치 수를 저장.
        answer = fibonacci(n);
        
        return answer;
    }
}