[백준 온라인 저지] 24416. 알고리즘 수업 - 피보나치 수 1

오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍으로 구하는 알고리즘을 배웠다. 재귀호출에 비해 동적 프로그래밍이 얼마나 빠른지 확인해 보자.

// 피보나치 수 재귀호출 의사 코드는 다음과 같다.
fib(n) {
    if (n = 1 or n = 2)
    then return 1; # 코드1
    else return (fib(n - 1) + fib(n - 2));
}

// 피보나치 수 동적 프로그래밍 의사 코드는 다음과 같다.
fibonacci(n) {
    f[1] <- f[2] <- 1;
    for i <- 3 to n
        f[i] <- f[i - 1] + f[i - 2]; # 코드2
    return f[n];
}

 

1. 입력

- 첫째 줄에 n(5 ≤ n ≤ 40)이 주어진다.

 

2. 출력

- 코드1 코드2 실행 횟수를 한 줄에 출력한다.

 

3. 예제

 

4. 코드

import java.util.*;
class Main{
    static int count1 = 0;
    static int count2 = 0;
    
    public static void main(String[] args){
        int n = new Scanner(System.in).nextInt();
        fib(n); fibonacci(n);
        System.out.print(count1+" "+count2);
    }
    
    static void fib(int n){
        if(n<=2) count1++;
        else {fib(n-1); fib(n-2);}
    }
    
    static void fibonacci(int n){
        for(int i=2 ; i<n ; i++)
            count2++;
    }
}