피보나치 함수

피보나치 함수를 구하는 재귀함수 소스를 준다. 이 문제는 피보나치 함수의 재귀적 함수가 호출하는 fibo(0)과 fibo(1)이 몇 번 호출되는지 알아보라는 문제인데, 만약 저기 코드에서 return 0, 1이 되기전에 count변수를 줘서 countZero, countOne에 호출될 때 마다 숫자를 쌓아가게 되면 시간초과 에러가 뜰 것이다.(내가 그랬다.) fibo(40)을 구한다고 하면 시간이 꽤 걸리기 때문이다. 계산상의 중복을 메모리를 이용해 없애줘야 한다. fibo(40)은 fibo(39)의 fibo(38)의 결과를 알고 있다면 그 두 결과를 더해주면 된다. 즉 for문을 통해 40까지 dp를 활용해 쌓아나가면 시간절약이 가능하다.

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

            for (int i=0; i<n; i++) {
                int num = sc.nextInt();
                if (num == 0) {
                    System.out.println("1 0");
                }
                else if (num == 1) {
                    System.out.println("0 1");
                }
                else {
                    int[][] dp = new int[num+1][2];
                    dp[0][0] = 1;
                    dp[0][1] = 0;
                    dp[1][0] = 0;
                    dp[1][1] = 1;
                    for (int j=2; j<=num; j++) {
                        dp[j][0] = dp[j-1][0] + dp[j-2][0];
                        dp[j][1] = dp[j-1][1] + dp[j-2][1];
                    }
                    System.out.println(dp[num][0] + " " + dp[num][1]);


                }
            }
    }
}