[백준] 2748번 : 피보나치 수 2 자바(JAVA) 풀이

문제

---

---

 

피보나치는 재귀함수로 푸는 방식이 유명하기 때문에 자연스럽게 재귀함수로 풀 수도 있는데 

시간복잡도가 O(2^N) 가 되기 때문에 다른 방식으로 풀어주어야 한다. 

그래서 DP(Dynamic Programming, 동적계획법) 으로 풀어주었다.

 

DP(Dynamic Programming, 동적계획법) 이란 ?

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법.

나눠진 결과를 저장하여 다시 복잡한 문제를 해결할 때 그 결과값을 사용하는 것이 DP이다.

(결과를 배열에 저장해서 사용해주었다.)

 

DP 사용하는 이유?

일반적인 재귀 방식과 비슷하지만 재귀 방식은 동일한 간단한 문제들이 여러 번 반복되어 계산되기 떄문에 비효율적일 수 있다. 값을 저장해두고 사용한다면 불필요한 과정을 없앨 수 있어 시간복잡도를 줄일 수 있다.

재귀 방식 O(2^N) → 동적계획법 O(N) 으로 개선될 수 있다.

 

문제 탐색하기

• 입력 : 피보나치 수를 구하고 싶은 자연수 N (0 ≤ N ≤ 90)
• 출력 : N번째 피보나치 수

---

코드 설계하기

• 입력 N을 변수에 저장한다.
• DP 관계식을 구현하고, N번째 수 까지의 답을 순차적으로 탐색한다.
• 구해진 피보나치 수를 출력한다.

---

풀이 코드

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

public class Main {
	static long[] fiboArr; // DP의 경우 값이 커지기 때문에 long[] 배열을 많이 사용함
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		fiboArr = new long[n+1];
		
		long result = fibo(n);
		System.out.println(result);
	}
	
	public static long fibo(int n) {
		if(n<2) {
			return n;
		} else {
			if(fiboArr[n] > 0) { // 배열에 값이 저장되어있으면 반환
				return fiboArr[n];
			}else { // 값이 없으면 계산
				fiboArr[n] = fibo(n-1) + fibo(n-2);
				return fiboArr[n];				
			}
		}
	}
}