1. Problem 📃

[ 피보나치 함수 ]

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

[ 문제 ]

다음 소스는 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이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

2. Input 📇

[ 입력 ]

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

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

3. Output 📠

[ 출력 ]

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

4. Example 📚

[ 입출력 예시 ]

5. Solution 🔑

피보나치 함수를 그대로 만들어서 개수를 세면 시간초과가 걸린다.
N에 대한 피보나치 수열은 N부터 0까지 모두 한 번씩 거치는데, 이를 또 피보나치로 계속 나누면 중복되는 호출이 발생하는데 이를 줄이기 위해 한 번의 호출에서 몇 번 나오는지에 대한 값을 미리 저장한다.

1. 문제에서 N 값은 40이하의 수이므로 2차원 배열(dp)로 [40][2]을 설정해준다 2칸인 이유는 인덱스(N)에서 fibonacci(0)과 fibonacci(1)의 개수를 나타내기 위해 설정해주었다.
   
   
2. 거치지 않은 N 이하의 값들을 null로 표시해주기 위해 Integer 타입으로 선언해주었다.
   (int형 타입으로 선언해줄 시 -1로 표시하여 그 값은 1과 0의 개수를 탐색하지 않았다고 표시를 해줍니다.)
   
   
3. 해당 값의 [0]과 [1]이 탐색하지 않았다면(if 값==null) fibonacci 메서드를 해당 값-1 과 해당 값 -2의 값을 재귀한다. 이때 해당 값이 0과 1일 때 오류가 나므로, 0과 1은
   우리가 직접 0과 1의 개수를 세어 값을 대입해놓고 fibonacci(2)에서 걸려 그 아래의 값 탐색 시 인덱스 오류가 나지 않도록 해주었다.
   
   
4. 메인 메서드에서 테스트 케이스의 개수(T)를 입력 받고 어떤 값을 탐색할지에 대한 변수(val)을 입력 받아 메서드의 매개변수로 넣어 해당 val[0]/val[1]을 출력한다.

< N = 5를 예시로 들어 >

fibonacci(5)는 메서드를 N 이하에 대한 수들의 개수가 누적되어 구해질 것이다. 이때 한 번 거친 값은 더 이상 거치지 않아도 되므로 탐색 시간을 현저히 줄일 수 있다.

6. Code 💻

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

public class Main {
	
	static Integer[][] dp = new Integer[41][2];
	
	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];
	}
	
	public static void main(String[] args) throws IOException {
		
		dp[0][0] = 1;
		dp[0][1] = 0;
		dp[1][0] = 0;
		dp[1][1] = 1;
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int T = Integer.parseInt(st.nextToken());
		int val;
		for(int i=0; i<T; i++) {
			st = new StringTokenizer(br.readLine());
			val = Integer.parseInt(st.nextToken());
			fibonacci(val);
			System.out.println(dp[val][0] + " " + dp[val][1]);
		}
	}

}

7. Growth 🍄

• https://st-lab.tistory.com/124
  
  일반 피보나치 메서드를 만들어 풀어보고 시간 초과가 걸려서 한 번 탐색한 부분은 찾지 말아야 겠다는 생각을 했는데 코드로 구현해내지 못했다..
  위에 낯선 개발자님의 티스토리 블로그를 보고 풀어냈다.. 아직 재귀함수에 대해 이해가 어려운거 같다.