[백준 - 1003번] 피보나치 함수 - 자바(JAVA) 정리 및 해설 & 1일 1DP 2일차

오늘 풀어볼 문제는 피보나치 함수입니다. 역시 Dynamic Programming

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

1003번: 피보나치 함수

일단 이문제는 특이하게도 알고리즘을 보여주고 시작합니다. 

물론 이 알고리즘만 보고 풀수 있는 문제는 아닙니다.  ㅋㅋ

 

어떤 식으로 접근 했는지?

일단 제가 접근했었던 방식은 DP = Top-Down 이렇게 생각하다보니까 탑다운 방식으로 골라서 풀었는데, 그렇게 썩 좋은 방법은 아닌것 같습니다.

 

일단 첫번째로는 0을가지는 경우와 1를 가지는 경우를 분리해서 했습니다. 

두가지 인자를 한 함수에서 동시에 굴리는 방법이 영 생각이 안나서, 아예 0을 몇번 가지는 지 확인하는 재귀함수와 1을 몇번 가지는지 확인하는 재귀함수를 만들어서 두개의 재귀함수를 순서대로 진행시켰습니다. 

 

전체 재귀 탈출 요건은 fibo0-> 0의 갯수 체크하는 재귀에서는 n=0일때는 1 n =1일때는 0이라고 지정했습니다.

fibo1 -> 1의 갯수 체크하는 재귀에서는 그와는 반대로 만들어서 탈출 할 수 있게했고 그값을 지정될 수 있게끔 cnt배열에 저장했고 만약에 그 저장된 것이 없는 경우에는 -1로 표시해서 재귀함수로 들어 갈 수 있는 조건을 만들었습니다.

/** 2020. 2. 18. 오후 4:22:59
 * @author ventulus95
 */
package codeBaekJoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class No1003_Fibonacci {
	static int cnt0[] = new int[41];
	static int cnt1[] = new int[41];
	
	public static int fibo0(int n){
		if(n==1){
			return 0;
		}
		if(n==0){
			return 1;
		}
		if(cnt0[n-1] == -1 && cnt0[n-2] == -1){
			cnt0[n] = fibo0(n-1)+fibo0(n-2);
			return cnt0[n];
		}
		else if(cnt0[n-1] == -1){
			cnt0[n] = fibo0(n-1)+cnt0[n-2];
			return cnt0[n];
			
		}
		else if(cnt0[n-2] == -1){
			cnt0[n] = cnt0[n-1]+fibo0(n-2);
			return cnt0[n];
		}
		else{
			cnt0[n] = cnt0[n-1]+cnt0[n-2];
			return cnt0[n];
		}
	}
	
	public static int fibo1(int n){
		if(n==1){
			return 1;
		}
		if(n==0){
			return 0;
		}
		if(cnt1[n-1] == -1 && cnt1[n-2] == -1){
			cnt1[n] = fibo1(n-1)+fibo1(n-2);
			return cnt1[n];
		}
		else if(cnt1[n-1] == -1){
			cnt1[n] = fibo1(n-1)+cnt1[n-2];
			return cnt1[n];
			
		}
		else if(cnt1[n-2] == -1){
			cnt1[n] = cnt1[n-1]+fibo1(n-2);
			return cnt1[n];
		}
		else{
			cnt1[n] = cnt1[n-1]+cnt1[n-2];
			return cnt1[n];
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		Arrays.fill(cnt0, -1);
		Arrays.fill(cnt1, -1);
		cnt0[0] = 1;
		cnt1[0] = 0;
		cnt0[1] = 0;
		cnt1[1] = 1;
		for(int i =0; i<T; i++){
			int n = Integer.parseInt(br.readLine());
			fibo0(n);
			fibo1(n);
			System.out.println(cnt0[n]+" "+cnt1[n]);
		}

	}

}

 

후일담

막상 이걸 문제를 다풀고나니까, 대부분들의 사람들은 Bottom-Up 방식으로 문제를 풀엇는데, 그게 맞는것 같았다. 특히 이중배열로 숫자N에서의 0과 1갯수를 동시에 처리할 수 있었고 수가 작아서, 한번에 다 처리하기도 편했다. 

Top-down 방식은 위의 방식처럼, 세부적인 조건들이 많아서 경우를 잘쪼개서 처리해야하는데, 막상 숫자가 안클때는 Bottom-up이 더 직관적인것 같다.

 

 

결국 바텀업 방식으로 푸는게 맞는 것 같았다 ㅠ