[백준] 24416번 : 알고리즘 수업 - 피보나치 수 1 _ JAVA ( 주석 설명 )

1번

→ 기존 중복 계산이 포함된 재귀로 풀었던 문제를, DP(동적 프로그래밍)로 해결한 문제

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


public class Main {
    static int fib_count = 0;
    static int fibonacci_count = 0;
    static int[] ary;
    static int[] ary2;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //버퍼에서 데이터를 읽어오는 방식으로 속도가 빠르다.
        int N = Integer.parseInt(br.readLine());
        ary = new int[N+1];
        ary2 = new int[N+1];

        fib(N);
        fibonacci(N);
//        fibonacci2(N);

        System.out.println(fib_count);
        System.out.println(fibonacci_count);

//        System.out.println(fibonacci(N));
//        System.out.println(fibonacci2(N));
    }


    //재귀 방식
    private static int fib(int n) {
        if(n==1 || n==2) {
            fib_count++;
            return 1;
        }

        else
            return fib(n - 1) + fib(n - 2);
    }

    //Bottom-up 방식, 아래에서부터 차근차근 구한다.
    private static int fibonacci(int n) {
        ary[1]=1;
        ary[2]=1;

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

        return ary[n];
    }

    //Top-down 방식, 위에서부터 아래까지 내려가며 맨 아래가 구해졌을 시 다시 올라와 위의 값을 구한다.
    private static int fibonacci2(int n) {
        if(n<=2){
            ary2[1]=1;
            ary2[2]=1;
        }

        if(ary2[n]>=1)
            return ary2[n];

        ary2[n] = fibonacci2(n-1) + fibonacci2(n-2);

        return ary2[n];
    }
}