[백준 1003] 피보나치 함수

 

피보나치수열을 계산하는 함수 f(n) 을 수행했을때 호출되는 f(0), f(1) 의 개수를 정리한 표이다.

n	f(0)	f(1)
2	1	1
3	1	2
4	2	3
5	3	5
6	5	8
7	8	13
8	13	21

n=0, n=1 일때는 규칙성이 없어서 제외했다.

위 표대로 입력이 n 일때 f(n-1), f(n)을 출력해주면 된다.

 

 

public static final int MAX = 41;
    public static int dp[] = new int[MAX];
    
    public static int fibonacci(int n) {
        if(n==0) {dp[0] = 0; return 0;}
        if(n==1) {dp[1] = 1; return 1;}
        if(dp[n] != -1) return dp[n];
        
        int result = fibonacci(n-1) + fibonacci(n-2);
        dp[n] = result;
        return result;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int t = sc.nextInt();
        for(int i=0; i<MAX; i++) {
            dp[i] = -1;
        }
        
        while(t-->0) {
            int n = sc.nextInt();
            
            if(n == 0)
                System.out.println(1 + " " + 0);
            else if(n == 1)
                System.out.println(0 + " " + 1);
            else {
                fibonacci(n);
                System.out.println(dp[n-1] + " " + dp[n]);
            }
        }
}