[백준][JAVA] 1003번 : 피보나치 함수(동적계획법과 메모이제이션을 활용한 풀이)

오늘은 백준 1003번 피보나치 함수에 대한 리뷰

유튜브로 동적계획법(Dynamic Programming)과 이를 위한 메모이제이션, 테뷸레이션 등등을 배웠는데 마침 느낌상 정석 같은 풀이라서 기록을 남긴다.

 

문제가 길지만, 요약하자면 함수를 통해 피보나치 수를 구할 때, 0과 1이 몇번 호출되는지 구하는 문제

기본 재귀함수 등 여러시도를 해봤지만 시간 초과 때문에 동적계획법을 활용해야함. 그 외의 신박한 풀이들은 구글에 검색하면 고수님들이 많이 올려주셨음.

 

나는 초보라서 동적계획법을 떠올리기 힘들었고, 처음에는 그저 카운트 할려했는데 포기하고 검색해 보니 DP문제라고 해서 다시 혼자서 연구해서 풀어냈다.(시간 초과 때문이지 절대 구현을 못한 건 아님!!)

 

구현한 코드는 사실 간단하다.

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

public class Number_1003 {

	static Integer[] fibonacci0 = new Integer[41];
	static Integer[] fibonacci1 = new Integer[41];
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T = Integer.parseInt(br.readLine());
		fibonacci0[0] = 1;
		fibonacci0[1] = 0;
		fibonacci1[0] = 0;
		fibonacci1[1] = 1;
		
		for(int i = 0 ; i < T ; i++) {
			int N = Integer.parseInt(br.readLine());
			bw.write(String.valueOf(getFibonacci0(N) + " " + String.valueOf(getFibonacci1(N))) + "\n");
		}
		
		bw.flush();
		bw.close();
		br.close();
	}
	
	
	public static int getFibonacci0(int n) {	
    	if(fibonacci0[n] != null) {
    		return fibonacci0[n];
    	}else {
    		fibonacci0[n - 1] = getFibonacci0(n - 1);
    		fibonacci0[n - 2] = getFibonacci0(n - 2);
    		return fibonacci0[n - 1] + fibonacci0[n - 2];
    	}
	}
	
	public static int getFibonacci1(int n) {	
    	if(fibonacci1[n] != null) {
    		return fibonacci1[n];
    	}else {
    		fibonacci1[n - 1] = getFibonacci1(n - 1);
    		fibonacci1[n - 2] = getFibonacci1(n - 2);
    		return fibonacci1[n - 1] + fibonacci1[n - 2];
    	}
	}
}