[백준] 1003번 피보나치 함수

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

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] zero = new int[41];
        int[] one = new int[41];
        zero[0] = 1;
        one[0] = 0;
        zero[1] = 0;
        one[1] = 1;
        for(int i = 2; i <= 40; i++) {
            zero[i] = zero[i - 2] + zero[i - 1];
            one[i] = one[i - 2] + one[i - 1];
        }
        for(int i = 0; i < n; i++) {
            int num = in.nextInt();
            System.out.print(zero[num] + " " + one[num]);
            System.out.println();
        }
    }
}

 

제한시간이 0.25초이기 때문에 재귀함수로 직접 호출해서 호출될 때마다 count를 늘리는 방식으로는 할 수 없다.

따라서 동적 계획법을 사용해야하는데 그러기 위해서 규칙성을 찾았다.

fibonacci(0)은 fibonacci(0)을 1번, fibonacci(1)을 0번 호출한다.

fibonacci(1)은 fibonacci(0)을 0번, fibonacci(1)을 1번 호출한다.

그 다음부터는 호출하는 횟수가 피보나치 수열대로 간다.

즉 앞의 두 개의 호출 횟수를 더한 것이 호출 횟수가 된다.