[백준] 2748번: 피보나치 수 2 [JAVA-자바]

문제

www.acmicpc.net/problem/2748

2748번: 피보나치 수 2

 

Problem

• 피보나치를 구하는 가장 기본적인 DP 문제이다.

메모제이션을 안쓰면

시간복잡도 O(2^N)

메모제이션을 쓰면

시간복잡도 O(N) 

Solution

• DP를 이용해서 문제를 해결한다.

Code

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

public class Main {
	static long[] dp = new long[91];

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		dp[0] = 0;
		dp[1] = 1;

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

		Arrays.fill(dp, -1);

		System.out.println(fibonacci(n));
	}

	static long fibonacci(int n) {

		if (n == 0)
			return 0;
		if (n == 1)
			return 1;
		if (dp[n] == -1) {
			dp[n] = fibonacci(n - 1) + fibonacci(n - 2);
		}
		return dp[n];

	}
}