[백준] 2748 피보나치 수 2(Bronze.1) - DP(동적 계획법)

문제

피보나치 수 2

코드

이 문제는 재귀를 이용하여 풀 수 있다.
하지만 Memoization를 이용하는 DP를 이용하면 더 효율적으로 풀 수 있다.
DP 하향식 방법을 이용했고 작은 문제의 결과를 저장하기 위해 fibo[] 배열을 사용했다.

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

public class _2748_피보나치_수2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        long result = fibo(n);

        System.out.println(result);
    }

    public static long fibo(int n) {
        if (n <= 1) return n;

        // Memoization
        long[] fibo = new long[n+1];
        fibo[0] = 0;
        fibo[1] = 1;
        // 상향식 방법
        for (int i = 2; i <= n; i++) fibo[i] = fibo[i-2] + fibo[i-1];

        return fibo[n];
    }
}