[코딩테스트/백준 알고리즘] 1003 - 피보나치 함수 (자바, Java 풀이)

문제

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

1003번: 피보나치 함수

---

문제 설명

---

문제 풀이

 시간 제한이 엄격하기 때문에 실제로 피보나치 함수를 실행해서 풀 수는 없는 문제다. 전형적인 다이나믹 프로그래밍 문제였다.

		call 0	call 1
fibonacci(0)	fibonacci(0)	1	0
fibonacci(1)	fibonacci(1)	0	1
fibonacci(2)	fibonacci(1) + fibonacci(0)	1	1
fibonacci(3)	fibonacci(2) + fibonacci(1)	1	2
fiboncaai(4)	fibonacci(3) + fibonacci(2)	2	3

fibonacci(n)에서 0이 리턴된 횟수는 fibonacci(n-1)과 fibonacci(n-2)에서 0이 호출된 횟수를 더한 것과 같다.

fibonacci(n)에서 1이 리턴된 횟수를 fibonacci(n-1)과 fibonacci(n-2)에서 1이 호출된 횟수를 더한 것과 같다.

---

코드

import java.util.*;

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