[코딩테스트] 백준 24416 : 알고리즘 수업 - 피보나치 수 1 - 자바

문제 

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

 

문제분석

• 피나보치 수열을 계산할 때, 재귀적 방법과 동적 프로그래밍을 사용하여 두 방식의 호출횟수를 비교하는 문제
• 5 ≤ n ≤ 40

문제풀이

• 두 함수의 동작 횟수를 구하기 위한 두 변수 C1,C2 을 선언하고 문제에 나온 위치에 도달 시 증가처리해준다.
• 두 함수를 실행한다.
• C1, C2를 출력한다.

package backjoon.bronze.lv1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B24416_1 {
    static int C1 = 0;
    static int C2 = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        fib(n);
        fibonacci(n);
        System.out.println(C1 + " " + C2);
    }

		// 재귀
    public static int fib(int n) {
        if (n == 1 || n == 2) {
            C1++;
            return 1;
        } else {
            return (fib(n - 1) + fib(n - 2));
        }
    }

		// 동적 프로그래밍(DP)
    public static int fibonacci(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }

        int[] f = new int[n + 1];
        f[1] = f[2] = 1;

        for (int i = 3; i <= n; i++) {
            f[i] = f[i - 1] + f[i - 2];
            C2++;
        }

        return f[n];
    }
}