#프로그래머스_피보나치 수 - Java 자바

#유형 : 수학

#난이도 : LV2

# 피보나치 수열 개념을 이용하면 쉽게 풀 수 있다. 맨 처음 재귀를 이용한 탑다운으로 문제를 접근했으나, 시간 초과가 발생하여 배열을 사용하여 바텀업으로 접근하여 해결하였다. 코드는 탑다운, 바텀업 둘다 첨부하였다.

class Solution {
    static int arr[];
    public int solution(int n) {
        arr = new int[n+1];
        int answer = fibo_arr(n);
        
        return answer;
    }
    
    public static int fibo(int n){
        if(n == 1)
            return 1;
        else if(n == 2)
            return 1;
        else 
            return fibo(n-1) + fibo(n-2);
    }
    
    public static int fibo_arr(int n){
        for(int i=0; i<=n; i++){
            if(i == 0)
                arr[i] = 0;
            else if(i == 1)
                arr[i] = 1;
            else if(i == 2)
                arr[i] = 1;
            else{
                arr[i] = (arr[i-1] + arr[i-2]) % 1234567;
            }
        }
        return arr[n];   
    }
}