[BaekJoon] 1003 피보나치 함수

1.  문제 링크

2.  문제

요약

• n번째 피보나치 수열에서 0과 1이 호출되는 횟수를 구합니다.
• 입력: 첫번째 줄에는 테스트 케이스의 개수가 주어지고 그 다음 줄부터는 몇 번째 피보나치 수열인지 주어집니다.
• 출력: 테스트 케이스 순서에 맞게 0이 출력되는 횟수와 1이 출력되는 횟수를 출력합니다.

3.  소스코드

초기버전(시간 부족 이슈)

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

public class Main {
	public int fibo(int n, int index, int[] num_list) {
		if(n == 0) {
			num_list[index] += 1;
			return 0;
		} else if(n == 1) {
			num_list[index + 1] += 1;
			return 1;
		} else {
			return fibo(n - 1, index, num_list) + fibo(n - 2, index, num_list);
		}
	}
	
	public int[] getFibo(ArrayList<Integer> testcases) {
		int[] num_list = new int[testcases.size() * 2];
		for(int i = 0; i < testcases.size(); i++) {
			fibo(testcases.get(i), i * 2, num_list);
		}
		return num_list;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine());
		ArrayList<Integer> testcases = new ArrayList<Integer>();
		for(int i = 0; i < num; i++) {
			testcases.add(Integer.parseInt(br.readLine()));
		}
		Main m = new Main();
		int[] num_list = m.getFibo(testcases);
		for(int i = 0; i < testcases.size(); i++) {
			System.out.println(num_list[2 * i] + " " + num_list[2 * i + 1]);
		}
	}
}

최종버전

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class Main {	
	public int[] getFibo(ArrayList<Integer> testcases) {
		int[] num_list = new int[testcases.size() * 2];
		for(int i = 0; i < testcases.size(); i++) {
			if(testcases.get(i) == 0) {
				num_list[2 * i] = 1;
				num_list[2 * i + 1] = 0;
			} else if(testcases.get(i) == 1) {
				num_list[2 * i] = 0;
				num_list[2 * i + 1] = 1;
			} else if(testcases.get(i) == 2) {
				num_list[2 * i] = 1;
				num_list[2 * i + 1] = 1;
			} else {
				int prev = 1;
				int pre_prev = 1;
				int num_one = 0;
				for(int j = 3; j <= testcases.get(i); j++) {
					num_one = prev + pre_prev;
					int temp = prev;
					prev += pre_prev;
					pre_prev = temp;
				}
				num_list[2 * i] = pre_prev;
				num_list[2 * i + 1] = num_one;
			}
		}
		return num_list;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		ArrayList<Integer> testcases = new ArrayList<Integer>();
		for(int i = 0; i < num; i++) {
			testcases.add(Integer.parseInt(br.readLine()));
		}
		br.close();
		Main m = new Main();
		int[] num_list = m.getFibo(testcases);
		for(int i = 0; i < testcases.size(); i++) {
			bw.write(num_list[2 * i] + " " + num_list[2 * i + 1] + "\n");
		}
		bw.flush();
		bw.close();
	}
}

4.  접근

• 각각의 피보나치 수열은 (본인 - 1)번째의 피보나치 수열과 (본인 - 2)번째의 피보나치 수열을 호출하기 때문에 이를 이용하여 0과 1이 호출되는 횟수를 구합니다.
• 초기버젼에서는 재귀를 이용하여 피보나치 수열을 작성한 후, 0과 1이 호출될 때마다 정수형 배열을 만들어 1씩 증가시켜 몇 번 호출되었는지 확인하였습니다.
• 그런데 이렇게 진행할 경우 재귀호출을 이용하여 최종적으로 0과 1이 호출되어 최종 결과가 나올 때까지 함수가 재귀적으로 돌기 때문에 시간 부족의 문제가 발생하였습니다.
• 시간 부족을 줄이고자 기존 System.out.println()으로 출력하던 방식은 완전히 출력될 때까지 대기시간이 발생하기 때문에 BufferedWriter를 이용하여 출력을 진행하였고 기존에 재귀적으로 호출하여 값을 구했던 피보나치 수열을 변경하였습니다.
• 피보나치 수열을 실제로 진행하면서 0과 1이 호출된 횟수를 구하는 방법은 시간 부족 문제에 부딪힐 수 있기 때문에 규칙을 찾아서 이를 이용하여 호출된 횟수를 구하였습니다.
• 각 피보나치 수열에서 0과 1의 호출된 횟수를 계산하여보니

  N번째 피보나치 수열	3	4	5	6	7	8	9
  0이 호출된 횟수	1	2	3	5	8	13	21
  1이 호출된 횟수	2	3	5	8	13	21	34

• 위의 표와 같은 결과가 나왔는데, 이를 보니 0이 호출된 횟수가 이전 피보나치 수열에서 1이 호출된 횟수와 같음을 알 수 있었습니다.
• 이를 이용하여 위 표에 나와있지 않은 0,1,2번째 피보나치 수열은 미리 구해놓고 3번째 피보나치 수열부터는 1이 호출되는 횟수를 재귀가 아닌 반복문으로 (본인 - 1)번째 호출된 횟수와 (본인 - 2)번째 호출된 횟수만 이용하여 구한 후에, (본인 - 1)번째 호출된 횟수를 0이 호출된 횟수로 이용하면 0과 1이 호출된 횟수를 구할 수 있습니다.
• 위 방법을 이용하여 시간 부족의 문제를 해결할 수 있었습니다.