백준 1003번 피보나치 함수(자바) - DP

---

이 문제는 푸는 게 어렵지는 않지만 시간초과가 자꾸 나와서 푸는데 오래 걸렸다..

일단 fibonacci(0) 과 fibonacci(1)이 호출된 횟수를 각각 구해야 하므로 

2차원 배열을 활용하여 n에 대한 f(0), f(1) 횟수를 따로 구할 수 있도록 했다.

또한 재귀를 활용하여 구해야 하므로 fibonacci 함수가 int 배열을 return 하도록 했다.

또, 한 번 구한 dp값은 또 구할 필요가 없도록 하기 위해 dp[num][0]과 dp[num][1] 둘 중 하나 이상이 0인 경우에만

dp값을 구하도록 했다.(n이 2 이상인 경우 dp[n][0] dp[n][1] 값이 0인 경우가 없으므로 dp 값이 0인 경우 이미 한 번 계산된 dp 값으로 판단했다)

import java.util.Scanner;

public class Test {
    static int [][] dp = new int[41][2];
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        int numOfTestCase = scanner.nextInt();
        dp[0][0] = 1;
        dp[0][1] = 0;
        dp[1][0] = 0;
        dp[1][1] = 1;

        int n;
        for(int i = 0; i < numOfTestCase; i++) {
            n = scanner.nextInt();
            fibonacci(n);
            System.out.println(dp[n][0] + " " + dp[n][1]);
        }

    }

    public static int[] fibonacci(int num) {
        if(num > 1) {
            if(dp[num][0] == 0 || dp[num][1] == 0) {
                dp[num][0] = fibonacci(num - 1)[0] + fibonacci(num - 2)[0];
                dp[num][1] = fibonacci(num - 1)[1] + fibonacci(num - 2)[1];
            }
        }
        return dp[num];
    }
}