[백준] 자바 1003 피보나치 함수

피보나치 함수

 

문제

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

1 2 3 4 5 6 7 8 9 10 11

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이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열입니다.

위 문제는 해당 피 보나 치수에서 f(1), f(0)이 총 몇 번 불러지는 출력하는 문제인데, 피보나치수열을 분리하다 보면 나름의 규칙을 알 수 있었습니다.

피보나치 수	f(0) 호출 수	f(1) 호출 수
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3

위 표에서 알 수 있듯이, 피보나치 수뿐만 아니라, f(0) f(1) 호출 수도 이전항 두 개와 합하여진 결과였습니다.

따라서 코드를 아래와 같이 짜면

package javaBaekjoon;
import java.io.*;
import java.math.*;
import java.util.*;

public class Main {

	/*
	 * 1003 problem 피보나치 함수
	다음 소스는 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이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.
	 */

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int num = Integer.parseInt(br.readLine());
		int fibo = 0;
		int arr0[] = new int[41];//f(0) 호출 수
		int arr1[] = new int[41];//f(1) 호출 수
		arr0[0] = 1;
		arr0[1] = 0;
		arr1[0] = 0;
		arr1[1] = 1;
		//각 피보나치 수에 f(0),f(1) 값 배열.
		for(int i=2; i<=40; i++) {
			arr0[i] = arr0[i-1] + arr0[i-2];
			arr1[i] = arr1[i-1] + arr1[i-2];
		}
		//값 출력
		for(int i=0; i<num; i++) {
			fibo = Integer.parseInt(br.readLine());
			System.out.println(arr0[fibo]+ " " +arr1[fibo]);
		}
		bw.flush();
		bw.close();
	}
}