백준 1003번 피보나치 함수

기존의 피보나치 함수 자체를 구현하는 문제와 달리, N번째 피보나치 수를 계산하기 위해 호출되는 0번째 피보나치 수(0)과 1번째 피보나치 수(1)의 호출 횟수를 구하는 문제다.

 

N번 째 피보나치 수	fibonacci(0) 의 호출 횟수	fibonacci(1) 의 호출 횟수
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3
5	3	5
6	5	8
7	8	13
8	13	21

 

N번 째 피보나치 수를 구하기 위해 fibonacci(0)와 fibonacci(1)이 호출되는 횟수를 나열하였다.

 

신기하게도 각 호출횟수도 역시 피보나치 수열을 구성하고 있었다.

 

N번째 피보나치 숫자의 fibonacci(0) 호출 횟수를 fibonacci(N, 0) 이라고 한다면 다음과 같은 식을 작성할 수 있다.

• fibonacci(N, 0) = fibonacci(N-1, 0) + fibonacci(N-2, 0)
• fibonacci(N, 1) = fibonacci(N-1, 1) + fibonacci(N-2, 1)

import java.util.Scanner;

public class Main {

    static Integer[][] dp = new Integer[41][2];
    // dp[N][0] = N번째 피보나치 숫자를 계산하는데 호출되는 fibonacci(0)의 횟수
    // dp[N][1] = N번째 피보나치 숫자를 계산하는데 호출되는 fibonacci(1)의 횟수

    public static void main(String[] args) {

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

        Scanner in = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        int T = in.nextInt();

        for (int i = 0; i < T; i++) {
            int N = in.nextInt();

            fibonacci(N);

            sb.append(dp[N][0]+" "+dp[N][1]).append('\n');

        }
        System.out.println(sb);
    }

    public static Integer[] fibonacci(int n) {

        if (dp[n][0] == null && dp[n][1] == null) {
            dp[n][0] = fibonacci(n - 1)[0] + fibonacci(n - 2)[0];
            dp[n][1] = fibonacci(n - 1)[1] + fibonacci(n - 2)[1];
        }

        return dp[n];
    }
}