🔗 링크

https://www.acmicpc.net/problem/1003

✏️ 문제

재귀로 구현된 피보나치 함수를 사용할 때 종료 조건 fibonacci(0)과 fibonacci(1)이 몇 번 반복되는지 찾는 문제입니다.

🧠 접근

언제나 그렇듯 한번 써 봅시다.
피보나치 수를 구하는 함수를 f(n) $(n \ge 0)$ 이라고 합시다.

f(0) 은 종료 조건이므로 f(0) 1회,f(1) 0회입니다.
f(1) 은 종료 조건이므로 f(0) 0회,f(1) 1회입니다.
f(2) 는 f(1)과 f(0) 을 호출하므로 각각 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

피보나치 수열이 보이시나요?

f(0) 의 호출 횟수는 n = 0 일 때 1, n 이 1 이상일 때에는 f(n - 1) 이 되고, f(1) 의 호출 횟수는 아예 피보나치 수열을 따르고 있는 것이 보이죠.

따라서 피보나치 수열의 값을 미리 구해 놓고 위 조건에 따라 출력하면 됩니다.

// 피보나치 수열을 미리 구함
int[] fibonacci = new int[40 + 1];
fibonacci[1] = 1;
for (int i = 2; i <= 40; i++) 
	fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
    
(...)
for (int i = 0; i < testCase; i++) {
	(...)
	int fZero, fOne;
    if (input == 0) {
    	fZero = 1;
        fOne = 0;
    } else {
    	fZero = fibonacci[input - 1];
        fOne = fibonacci[input];
    }
    (...)
}
(...)

문제가 전부 해결되었습니다.

📄 전체 소스 코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder builder = new StringBuilder();
        int[] fibonacci = new int[40 + 1];
        fibonacci[1] = 1;
        for (int i = 2; i <= 40; i++) 
            fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
        
        int testCase = Integer.parseInt(reader.readLine());
        
        for (int i = 0; i < testCase; i++) {
            int input = Integer.parseInt(reader.readLine());
            int fZero, fOne;
            if (input == 0) {
                fZero = 1;
                fOne = 0;
            } else {
                fZero = fibonacci[input - 1];
                fOne = fibonacci[input];
            }
            builder.append(fZero + " " + fOne + "\n");
        } 
        System.out.print(builder.toString());
    }
}