[백준 1003번 : 실버3] 피보나치 함수 : DP(Java)

이번 문제는 약간 쉬웠던 문제 같았다.

첨엔 DP로 생각안하고 그냥 재귀함수만을 호출해 문제를 풀었다가 시간초과가 났는데 

DP를 적용해서 문제를 푸니 풀수가 있었다.

 

문제를 살펴보자.

 

문제

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

1 2 3 4 5 6 7 8 9 10 11

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이 출력되는 횟수를 공백으로 구분해서 출력한다.

 

 

 

문제 접근 방법

이번 문제는 피보나치 함수에서 적용하는 DP와 같은 방식으로 적용했다.

https://wpioneer.tistory.com/120

[자료구조] 동적계획법 알고리즘 ( Dynamic Algorithm)

위 링크를 보고 오면 좀더 내가 작성한 소스를 이해가 빠를것같다.

 

나의 방식은 아래와 같다.

 

2차원 배열을 만들어서 해당 수에 호출되는 0과1의 호출 개수를 저장해서 사용하는것이다.

n이 3일때 만든 2차원 배열

 

소스는 아래와 같다.

 

import java.util.Scanner;

public class Run {
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Run a = new Run();
		Scanner sc = new Scanner(System.in);
		int su = sc.nextInt(); //테스트케이스 수 입력
		int[] testCase = new int[su];
		//테스트 케이스 입력
		for(int i = 0; i<su;i++) {
			testCase[i] = sc.nextInt();
		}

//		int su = 3;
//		int[] testCase = {0,1,3};
		for(int i = 0; i<su;i++) {
			int[][] dp = new int[testCase[i]+1][2]; //0과 1의 호출 수를 입력 받을 배열
			int[] answer = a.fibonacci(testCase[i],dp);
			System.out.print(answer[0]+" ");
			System.out.println(answer[1]);
		}
	}

	public int[] fibonacci(int n,int[][] ot) {
		//해당 칸에 0과 1이 적힌 배열이 비어 있는지를 확인
		if(ot[n][0] <= 0 && ot[n][1] <= 0) {
			if(n == 0) { //0이라면
				ot[n][0] = 1; //0칸에 1 입력하고
				return ot[n];//ot[0] 배열 리턴
			}else if(n == 1) {//1이라면
				ot[n][1] = 1; //1칸에 1 입력하고
				return ot[n];//ot[1] 배열 리턴
			}else {
				int[] temp1 = fibonacci(n-1,ot);
				int[] temp2 = fibonacci(n-2,ot);
				
				//받은 배열을 합쳐서 ot[n] 베열안에 값을 넣는다.
				ot[n][0] = temp1[0] + temp2[0];
				ot[n][1] = temp1[1] + temp2[1];
				
				return ot[n];
			}
		}else {//해당칸이 비어 있지 않다면 해당 칸에 있는 배열 return
			return ot[n];
		}
	}
}

 

 

 

 

 

느낀점

 

1. DP는 꼭 전달 받은 숫자만큼의 배열을 꼭 만들어줘야 한다.