📣
Baekjoon에서 PASS된 코드만 업데이트합니다.
알고리즘을 먼저 풀이하는 언어(Java)가 정해져있어,
풀이 언어(Python, C++, Java)가 모두 업데이트될 때까지는 시간이 걸릴 수 있습니다.

문제 제시

문제

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

문제 풀이

피보나치는 연습이나 과제, 그리고 기초 알고리즘 문제로 정말 많이 푸는 문제라고 생각합니다.
하지만, 이 문제는 그냥 피보나치를 구하라는 문제와는 조금 다르죠.

단순히 피보나치 함수의 결과를 확인하는 것이 아닌 f(0)과 f(1)이 호출되는 횟수를 보여주어야 합니다.

손으로 간단하게 확인할 수 있는 피보나치 5번째까지 작성을 해보았습니다.
그리고 순서대로 그 규칙을 적어보았습니다.

f(0)과 f(1)을 호출한 횟수를 나열해보았습니다. f(5)까지 작성했지만, 벌써 특징이 보이지 않으시나요?
피보나치의 f(n) = f(n-1) + f(n-2)의 특성이 동일하게 나타나는 걸 볼 수 있습니다.

굳이 재귀함수를 진행하면서 카운팅을 할 필요없이 이 특성을 통해 바로 확인할 수 있습니다.
0와 1을 저장할 수 있는 2차원 배열을 작성해서 진행하면 됩니다.

Default 값으로 0을 저장하는 차원의 0번째에는 1로 (1번 호출), 1을 저장하는 차원에는 1번째에 1로 초기화해서 작성하면 됩니다.

주어진 횟수만큼 반복을 하지만, 입력된 수만을 찾으면 되기에 엄청 큰 수까지를 다 구할 필요는 없습니다.
피보나치는 0부터 시작하므로 N을 구하려면 N+1개가 필요하게 됩니다.

이 특성을 정리하면,

1. 0/1을 호출하는 횟수 역시 f(n) = f(n-1) + f(n-2)의 특성을 갖고 있다.
2. 0부터 N까지를 확인해야하기에 N+1개를 확인해야 한다.
3. f(0)을 호출하는 기본값은 0번째일 때 1번 호출한다.
4. f(1)을 호출하는 기본값은 1번째일 때 1번 호출한다.

2~4번의 특성에 의해 N+1 x 2 차원의 배경으로 정리할 수 있습니다.
이 내용을 순차대로만 코드화 한다면 쉽게 정리될 수 있습니다.

문제 코드

Java

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;

public class Main {

  static int N, NUM;
  static int[][] fibo;
  static StringBuilder sb = new StringBuilder("");

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

    N = Integer.parseInt(br.readLine());

    for (int n = 1; n <= N; n++) {
      NUM = Integer.parseInt(br.readLine());

      fibo = new int[NUM + 1][2]; // 0 ~ N까지
      fibo[0][0] = 1;

      if (NUM > 0) fibo[1][1] = 1;

      for (int i = 2; i <= NUM; i++) {
        fibo[i][0] = fibo[i - 1][0] + fibo[i - 2][0];
        fibo[i][1] = fibo[i - 1][1] + fibo[i - 2][1];
      }
			
      sb.append(fibo[NUM][0]).append(" ").append(fibo[NUM][1]);

      if (n < N) sb.append("\n");
    }
		
    System.out.println(sb.toString());
  }
}

제출 결과