[JAVA] 2748번 피보나치 수2

DP를 처음 접하는 사람에게 추천하는 문제 중 하나.

 

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

2748번: 피보나치 수 2

 

1. 재귀함수

: 피보나치의 수는 재귀함수로도 풀 수 있는 문제지만,

지수적 함수를 현실에서 구할 수 없다고 판단 >> DP 활용!

 

동빈나 동적 프로그래밍 피보나치 수열 강좌 유튜브 캡처

 

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

public class Main{
	 
	public static void main(String[] args) throws IOException  {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());	
		
		int result = fibo(N);
		
		System.out.println(result);
	}

	private static int fibo(int n) {
		
		if(n<=2) {
			return 1;
		} else {
			return fibo(n-2) + fibo(n-1);
		}
	}
}

 

2. DP

 

중복 호출이 일어나 비효율적이므로 어떠한 값을 계산한 적이 있다면 그 값을 활용

 

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

public class Main{
	 
	public static void main(String[] args) throws IOException  {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());	
		
		int result = fibo(N);
		
		System.out.println(result);
	}

	private static int fibo(int n) {
		
		int[] dp = new int[91];
		
		if(n==2 || n==1) {
			return 1;
		} else if(dp[n]<=0){
			dp[n] = fibo(n-2) + fibo(n-1);	//값이 없다면 재귀함수 호출
		} 

		return dp[n];
	}
}

백준 결과 >> 메모리 초과

 

 

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

public class Main{
	static long[] dp;
	
	public static void main(String[] args) throws IOException  {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());	
		
		dp = new long[N + 1];

		for(int i = 0; i < N + 1; i++) {
			dp[i] = -1;
		}
		
		dp[0] = 0;
		dp[1] = 1;
		System.out.println(fibo(N));
	}

	public static long fibo(int N) {
		
		if(dp[N]==-1){
			dp[N] = fibo(N-1) + fibo(N-2);	//값이 없다면 재귀함수 호출
		} 
		return dp[N];
	}
}

>> 백준 결과

2748

맞았습니다!!

14288 KB

128 MS