[Java] 백준 1003번 피보나치 함수(DP, Top-Down, Bottom-Up)

[Java]  백준 1003번 피보나치 함수(DP, Top-Down, Bottom-Up)

* 학습 목적의 게시물이나 혹시 이 게시물이 문제가 된다면 언제든 연락 부탁드립니다.

* 더 나은 풀이를 위한 훈수, 조언 등 모두 환영합니다!

문 제 

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입 력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출 력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

[문제 링크] 백준 1003번 피보나치 함수

---

문제 해석

• 현재 직면한 문제가 작은 문제들로 이루어진 하나의 함수로 표현될 수 있기에 DP로 풀 수 있다.
• 이 문제에서는 연습 겸 Top-Down, Bottom-Down 두 가지로 모두 풀어보았다.

해결 방법

[공통]

• 값을 저장할 배열을 만든다.
  • 저장될 수 있는 값이 0 ~ 40까지이기에 41칸으로 만든다.
  • 0과 1이 나오는 수를 세야함으로 기록해야할 것이 2개이기에 2차원 배열로 만든다.
• 기저값은 사전에 저장시켜둔다.(0과 1을 넣었을 때)

[DP Top-Down]

• 2 미만(기저값)일 경우, 해당 값 반환
• 주어진 n의 결과가 저장되어 있을 경우, 해당 값을 배열에서 꺼내 반환한다.
• 없다면 해당 값을 계산하여 배열에 저장하고, 그 값을 반환한다.

[DP Bottom-UP]

• 기저값 이후 부터의 값을 기저값을 활용하여 계산해가며 값을 저장하는 배열을 채워나간다.

참고사항

• 추가 공부 필요내용 : 동적 프로그래밍, 분할 정복

전체 코드

package baekjoon;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
	
public class B1003 {
	
	static int[][] topDownMemo;
	static int[][] bottomUpMemo;
	static final int MAXTESTCOUNT = 40;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int numberOfTests = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < numberOfTests; i++) {
			
			topDownMemo = new int[MAXTESTCOUNT + 1][2]; 
			bottomUpMemo = new int[MAXTESTCOUNT + 1][2]; 

			int givenNum = Integer.parseInt(br.readLine());
			int[] answer = topDownFibonacci(givenNum);
//			int[] answer = bottomUpFibonacci(givenNum);
			
			bw.write(String.valueOf(answer[0]) + " ");
			bw.write(String.valueOf(answer[1]) + "\n");			
		}
		bw.flush();
		bw.close();
		br.close();
	}
	
	// DP Top-Down을 사용
	static int[] topDownFibonacci(int givenNum) {
		// 기저 상태 사전 저장
		topDownMemo[0][0] = 1;
		topDownMemo[0][1] = 0;
		topDownMemo[1][0] = 0;
		topDownMemo[1][1] = 1;
		
		if(givenNum < 2) {
			// 기저값 도달시, 사전값 반환
			return topDownMemo[givenNum];
		} else if(topDownMemo[givenNum][0] > 0 && topDownMemo[givenNum][1] > 0) {
			// 메모에 계산된 값이 있으면 바로 반환
			return topDownMemo[givenNum];
		}
		
		// 재귀를 사용
		topDownMemo[givenNum][0] = topDownFibonacci(givenNum - 1)[0] + topDownFibonacci(givenNum - 2)[0];
		topDownMemo[givenNum][1] = topDownFibonacci(givenNum - 1)[1] + topDownFibonacci(givenNum - 2)[1];
		
		return topDownMemo[givenNum];
	}
	
	// DP Bottom-Up을 사용
	static int[] bottomUpFibonacci(int givenNum) {
		// 기저 상태 사전 저장
		bottomUpMemo[0][0] = 1;
		bottomUpMemo[0][1] = 0;
		bottomUpMemo[1][0] = 0;
		bottomUpMemo[1][1] = 1;
		
		// 반복문을 통해 table을 채워나감
		for(int i = 2; i <= givenNum; i++) {
			bottomUpMemo[i][0] = bottomUpMemo[i - 1][0] + bottomUpMemo[i - 2][0];
			bottomUpMemo[i][1] = bottomUpMemo[i - 1][1] + bottomUpMemo[i - 2][1];
		}
		
		return bottomUpMemo[givenNum];
	}
}