백준 2748번 피보나치 수열 동적계획법 활용 2가지 풀이 ( Java )

2748번: 피보나치 수 2

- Top-Down ( 재귀 함수 호출 ) 방식

 

import java.io.*;
 
public class Main {
    
    static long[] memo; 
    // 메모이제이션 배열 생성
    static long fibonacci(int n) {
        if(n<=1) {
            // 0과 1은 답을 구할 수 없는 가장 작은 수
            return n;
        }else {
            if(memo[n]>0) {
                // 메모 되어 있다면
                return memo[n];
                // 메모 값을 리턴
            }
 
            memo[n] = fibonacci(n-1) + fibonacci(n-2);
            // 재귀 호출 보내서 받은 값을 메모에 담고
            return memo[n];
            // 메모를 리턴
        }
    }
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // reader writer 생성
        memo = new long[91];
        
        int n = Integer.parseInt(br.readLine());
        
        long answer = fibonacci(n);
        
        bw.write(String.valueOf(answer));
        bw.flush();
 
    }
 
}

 

- Bottom-Up ( 반복문 활용 ) 방식

 

public class FibonacciNumber2BottomUp {
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // reader writer 생성
 
        int n = Integer.parseInt(br.readLine());
 
        long[] fibonacci = new long[91];
 
        fibonacci[0] = 0;
        fibonacci[1] = 1;
 
        for (int i = 2; i <= n; i++) {
            fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
        }
        
        bw.write(String.valueOf(fibonacci[n]));
        bw.flush();
 
    }
 
}