피보나치 함수

백준 [1003] 피보나치 함수

풀이

f(0) = 0
f(1) = 1
f(2) = f(1) + f(0)
f(3) = f(2) + f(1) = 2f(1) + f(0)
f(4) = f(3) + f(2) = 3f(1) + 2f(0)
f(5) = f(4) + f(3) = 5f(1) + 3f(0)
…

f(0)과 f(1)의 갯수는 아래의 규칙을 갖는다.
f(0) -> 1, 0, 1, 1, 2, 3, 5, 8, 13 ..
f(1) -> 0, 1 ,1, 2, 3, 5, 8, 13, 21 …

소스코드

import java.util.Scanner;

public class Main {
    private static int zeroCnt;
    private static int oneCnt;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();
        for (int tc = 0; tc < T; tc++) {
            int N = sc.nextInt();

            zeroCnt = 0;
            oneCnt = 0;

            fibonachi(N, 1, 0, 1);

            System.out.println(zeroCnt + " " + oneCnt);
        }
    }


    // f(0) -> 1, 0, 1, 1, 2, 3, 5, 8, 13 ..
    // f(1) -> 0, 1 ,1, 2, 3, 5, 8, 13, 21 ...
    private static void fibonachi(int n, int idx, int val1, int val2) {
        if (n == 0) {
            zeroCnt = 1;
            oneCnt = 0;
            return;
        }
        if (idx == n) {
            zeroCnt = val1;
            oneCnt = val2;
            return;
        }

        fibonachi(n, idx + 1, val2, val1 + val2);
    }
}