피보나치 함수

문제

다음 소스는 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이 출력되는 횟수를 공백으로 구분해서 출력한다.

예제 입력 1

3
0
1
3

예제 출력 1

1 0
0 1
1 2

예제 입력 2

2
6
22

예제 출력 2

5 8
10946 17711

문제 풀이

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

public class BJ1003 {
    static int[][] memo;
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb=new StringBuilder();

        int T=Integer.parseInt(br.readLine());
        memo=new int[41][2];
        memo[0][0]=1;
        memo[0][1]=0;
        memo[1][0]=0;
        memo[1][1]=1;
        for(int t=0;t<T;t++){
            int num=Integer.parseInt(br.readLine());

            fibonacci(num);
            sb.append(memo[num][0]+" "+memo[num][1]+"\n");
        }
        System.out.print(sb);
    }

    private static int[] fibonacci(int n) {
        if(memo[n][0]==0 && memo[n][1]==0){
            memo[n][0]=fibonacci(n-1)[0]+fibonacci(n-2)[0];
            memo[n][1]=fibonacci(n-1)[1]+fibonacci(n-2)[1];
        }
        return memo[n];
    }
}

문제에 주어진 재귀함수를 이용하여 n==0일때, n==1 일때 각각 변수의 값을 추가해줘서 답을 출력하는 방향으로 구현했는데 시간초과가 발생했다.

시간초과를 줄이기 위한 방법을 찾아보다가 문제가 다이나믹 프로그래밍으로 분류되어있다는 것을 확인했다.

다이나믹 프로그래밍 방식을 찾아보다가 메모제이션 방식을 알아내어 사용했다. 메모제이션은 이전의 값을 기억해뒀다가 그대로 가져다 쓰는 방식으로 memo라는 이중배열을 만들어 0과 1이 각각 몇 번 나왔는지 값을 넣어주고 피보나치 수열을 만들어 해당하는 숫자에서 0과 1이 얼마나 나오는지 확인할 수 있다.

0과 1일때 각각 1과 0을 초기화해주고 피보나치수열을 구하는 재귀함수를 이용하면 시간초과 없이 문제를 해결할 수 있다.