[JAVA] 백준 알고리즘 1003 : 피보나치 함수

fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

문제

소스

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
	Scanner sc = new Scanner(System.in);
	int t = sc.nextInt();
        String result;

        for (int i=0; i<t; i++) {
            int n = sc.nextInt();
            result = f(n) + " " + f(n+1); // N의 f(1) 은 N+1의 f(0)의 값과 같다.
	    System.out.println(result);
        } 	
    }
    
    // 피보나치 함수
    public static int f(int n) {
        
        // n이 0일 경우 초기값
        int a = 1; // f(0)
        int b = 0; // f(1)
        int c = 1; // f(0)+f(1)

        if (n == 0) {
            return 1;
        } else if (n == 1) {
            return 0;
        } else {
            for (int i=1; i<=n; i++) {
                a=b;
                b=c;
                c=a+b;
            }
            return a;
        }
    }
}

구현한 함수 요약 설명

N	f(0) 카운트	f(1) 카운트	f(0)+f(1)
0	1	0	1
1	0	1	1
2	1	1	2
3	1	2	3
4	2	3	5
5	3	5	8
6	5	8	13

f(0) = a, f(1) = b, f(0)+f(1) = c 라고 할 때,  N+1은 다음과 같다.

a=b;

b=c;

c=a+b;

즉,  N의 f(1) 은 N+1의 f(0)의 값과 같다.

실패 소스 (시간 초과)

import java.util.*;

public class Main {
    
    static int arr[] = new int[2];
    
    public static void main(String[] args) throws Exception {
	Scanner sc = new Scanner(System.in);
	int t = sc.nextInt();
        
        for (int i=0; i<t; i++) {
            arr[0] = 0; // 호출된 0의 수
            arr[1] = 0; // 호출된 1의 수
            fibonacci(sc.nextInt());
		    System.out.println(arr[0] + " " + arr[1]);
        } 	
    }
    
    // 피보나치 함수
    public static int fibonacci(int n) {
        if (n == 0) {
            arr[0]++;
            return 0;
        } else if (n == 1) {
            arr[1]++;
            return 1;
        } else {
            return fibonacci(n-1) + fibonacci(n-2);
        }
    }
}

출처

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