1003 피보나치 함수 (JAVA)

• 6의 입력은 5 8 을 출력해야 한다.
• 피보나치 수열의 6번째 값은 8이고 5번째 값은 5이다.
• 즉 n 과 n-1 에 대한 피보나치 수열을 구하면 되는 문제.

• 배열로 구현하면 시간복잡도를 고려하지 않아도 되지만, 재귀로 구현할 시에는 메모이제이션으로 불필요한 호출을 방지해야 한다.

import java.util.Scanner;

public class Main {
    static int[] fibo = new int[41];
    static int fibonacci(int n){
        if(fibo[n] != 0)
            return fibo[n];
        if(n==1)
            return fibo[1] = 1;
        else if(n==2)
            return fibo[2] = 1;
        else
            return fibo[n] = fibonacci(n-1) + fibonacci(n-2);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        while(n-->0) {
            int i = sc.nextInt();
            if (i == 0)
                System.out.println(1 + " " + 0);
            else if (i == 1)
                System.out.println(0 + " " + 1);
            else
                System.out.println(fibonacci(i - 1) + " " + fibonacci(i));
        }
    }
}