문제

문제 이해

재귀함수로 구현된 피보나치 함수에서 0과 1을 호출하는 횟수를 출력하는 문제이다. 이 문제의 경우 메모이제이션과 다이나믹 프로그래밍 알고리즘을 이용하여 해결할 수 있다. 다이나믹 프로그래밍의 해결 방법을 적용시켰다.

다이나믹 프로그래밍의 해결방법을 생각해낸 이유는 위에서 피보나치 함수의 동작 원리를 살펴보면 트리구조로 이전에 출력했던 결과물을 다른 부모 노드에서 계속해서 출력했기 때문에 이전에 결과값을 이용할 수 있다는 점에서 생각하게 되었다.

코드 작성

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Fibonacci {
  static int T, N;
  static Integer[][] dp = new Integer[2][41];

  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());
    dp[0][0] = 1;
    dp[0][1] = 0;
    dp[1][0] = 0;
    dp[1][1] = 1;

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

  private static void fibonacci(int n) {
    if (dp[0][n] != null && dp[0][1] != null)
      return;
    for (int i = 2; i <= n; i++) {
      if (dp[0][i] == null && dp[1][i] == null) {
        dp[0][i] = dp[0][i - 2] + dp[0][i - 1];
        dp[1][i] = dp[1][i - 2] + dp[1][i - 1];
      }
    }
  }
}

코드 설명

N	0	1
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3

다음과 같이 N = N-2[0, 1] + N-1[0,1] 의 값을 알 수 있다. 이를 이용하여 다이나믹 프로그래밍에 사용할 수 있다. 이를 이용하여 2차원 배열 dp를 선언하였다. int 타입으로 선언할 경우 빈 배열 값에 0이 들어가게 되므로 다른 값으로 초기화를 할 필요가 있지만 Integer로 선언할 경우 null로 기본 값이 들어가게 되므로 null 체크를 이용할 수 있다.
null 값을 체크하여 해당 N의 값이 없을 경우 N-2번째 dp 값과 N-1 번째 dp값을 dp[N]에 넣어 두고 이를 출력하면 결과값을 얻을 수 있다.