[백준] 2748 : 피보나치 수 2 JAVA 풀이

동적 계획법은 크게 재귀(Top-Down)방식과 반복문(Bottom-Up)방식으로 나뉜다.

재귀 방식은 큰 문제를 작게 쪼개서 가장 하위 문제부터 풀어나가는 것인데,

동적 계획법은 이미 풀린 하위 문제를 다시 반복하지 않고 그 값을 재활용하고,

이를 메모이제이션(Memoization)이라고 한다.

 

동적 계획법 연습을 위해 Top-Down과 Bottom-Up 두 방식으로 문제를 풀어봤다.

 

 

 

먼저 재귀를 활용하는 Top-Down 방식이다.

이전에도 재귀를 이용해 피보나치 수를 구한 적이 있는데, 그때는 그냥 단순히 재귀를 해서 값을 구할 뿐이었다.

하지만 이 문제의 카테고리는동적 계획법이고 그런 방식으로 풀면 시간초과라는 결과가 나온다.

따라서 한 번 해결한 하위 문제의 값을 재활용하는 방식으로 문제를 풀었다.

 

우선 문제에서 주어질 수 있는 값이 int가 받아들일 수 있는 범위를 넘어서기 때문에

long 타입의 dp 배열을 생성한다.

그리고 처음 구하는 값일 때만 피보나치 수를 계산하고, 이미 계산한 적이 있던 값은 재활용하도록 했다.

import java.io.IOException;
import java.io.BufferedReader;
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());
        // N번째 피보나치 수를 구하기 위해서 배열 생성
        dp = new long[N+1];
        // 배열을 -1로 초기화해서 이미 구한 값인지 판단할 수 있도록 함
        for(int i=0;i<N+1;i++) dp[i] = -1;
        // 0번째 피보나치 수는 0
        dp[0] = 0;
        // 1번째 피보나치 수는 1
        dp[1] = 1;
        
        System.out.println(fibo(N));
    }
    static long fibo(int n){
    	// 이전에 계산한 적이 없다면
        if(dp[n]==-1){
        	// 앞선 두 개의 수를 더해 피보나치 수를 구함
            dp[n] = fibo(n-1)+fibo(n-2);
        }
        // 이미 계산한 적이 있다면 그 값을 반환함
        return dp[n];
    }
}

---

 

반복문을 사용하는 Bottom-Up 방식이다.

 

마찬가지로 long형의 dp 배열을 생성하고,

0번째와 1번째 피보나치수를 초기화해줬다.

그리고 반복문을 돌면서 2번째부터 N번째 피보나치수를 구해줬다.

이런 방식으로 하면 자연스럽게 앞에서 구한 값을 활용하게 된다.

import java.io.IOException;
import java.io.BufferedReader;
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());
        long[] dp = new long[N+1];
        dp[0] = 0;
        dp[1] = 1;
        
        for(int i=2;i<dp.length;i++){
            dp[i] = dp[i-1]+dp[i-2];
        }
        
        System.out.println(dp[N]);
    }
}