문제: https://www.acmicpc.net/problem/1003
참고: https://st-lab.tistory.com/124

설명

첫번째 방법은 fibonacchi(1)과 fibonacchi(0)이 호출될 때마다 각각의 count 변수를 1씩 증가하였다. 이렇게 했을 때, 시간초과가 발생했다.

이 문제를 주어진 시간 복잡도내에 풀기 위해서 dynamic programming 기법을 사용해야 한다.
우리가 알고 있는 피보나치를 살펴보면,
fibonacci(3)은 fibonacchi(2)와 fibonacci(1)을 호출하고, fibonacci(2)는 fibonacci(1)과 fobonacchi(0)을 추출한다.
이렇게 fibonacchi(n)을 호출하면 이전에 호출된 연산들이 중복되어 호출된다. 특히 fibonacci(1)과 fibonacchi(0)은 엄청난 중복 호출을 하게 되는데 이를 그림으로 표현한 것은 다음과 같다.

그림과 같이 중복되어 호출되는 것을 확인할 수 있다. 이렇게 중복된 함수 호출은 시간 복잡도를 증가한다. 우리는 자주 사용되는 두 값을 미리 계산해두고, 이를 재활용하겠다.

• N은 0일 때, 0과 1호출 횟수와 N은 1일 때 0과 1 호출 횟수를 미리 저장해둔다.
• N이 최대 40까지 주어지고, 각 N에 0과 1이 호출된 횟수를 담기 위한 2차원 배열을 만든다.
  • NULL 체크를 하기위해 Integer[][] 배열로 만든다(int[][] 배열을 사용한다면 모든 배열의 값을 -1과 같은 값으로 초기화한다.).
• 탐색하지 않은 값에 대해, N에 대한 0 호출 횟수와 1 호출 횟수를 재귀호출한다.

코드

public class P1003 {
    static int T;
    static int N;
    static int dp[][] = new int[41][2];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        dp[0][0] = 1;
        dp[0][1] = 0;
        dp[1][0] = 0;
        dp[1][1] = 1;

        T = Integer.parseInt(st.nextToken());

        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            fibo(N);
            System.out.println(dp[N][0] + " " + dp[N][1]);
        }
    }

    private static void fibo(int n) {
        for (int i = 2; i <= n; i++) {
            dp[i][0] = dp[i - 1][0] + dp[i - 2][0];
            dp[i][1] = dp[i - 1][1] + dp[i - 2][1];
        }
    }
}

+) 처음에 생각했던 방법을 DP로 수정해 보았다.
앞에서 했던 배열은 만드는 것과 같다. 배열로 표현한 것을 두 개의 변수로 표현한 것으로 보면 된다.

public class P1003 {
    static int T;
    static int N;
    static int n_zero, n_one;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        T = Integer.parseInt(st.nextToken());

        for (int i = 0; i < T; i++) {
            n_zero = 0;
            n_one = 0;
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            fibo(N);
            System.out.println(n_zero + " " + n_one);
        }
    }

    private static void fibo(int n) {
        int temp1 = 0;
        int temp2 = 1;
        int temp;
        if (n == 0) {
            n_zero += 1;
            return;
        } else if (n == 1) {
            n_one += 1;
            return;
        } else {
            for (int i = 1; i < n; i++) {
                temp = temp1 + temp2;
                temp1 = temp2;
                temp2 = temp;
            }
            n_zero = temp1;
            n_one = temp2;
        }
    }
}