[백준/1003/Java] 피보나치 함수 - 2가지 풀이법

 

 

문제:

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

 

 

문제분석

다음 소스는 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번 출력됩니다.

fibonacci(N)을 호출하였을 때, 0과 1이 각각 몇 번 출력되는지 구하는 문제입니다.

 

입력

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

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

 

출력

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

 

풀이

이 문제는 C++ 소스를 보시면 0이 출력되는 경우는 if (n == 0)이므로 파라미터가 0으로 호출되는 경우입니다.

1이 출력되는 경우는 if (n == 1)이므로 파라미터가 1로 호출되는 경우입니다.

fibonacci(1)을 붉은 색, fibonacci(0)을 파란색으로 표시하면 이렇게 됩니다.

 

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출합니다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출합니다.

0, 1이 출력되는 경우를 보기 위하여 피보나치 함수를 모두 호출하면서 계산하기엔 시간이 오래 걸립니다.

따라서, 문제 푸는 것에 집중하여 0, 1이 표시되는 것을 정리하면 이렇게 됩니다.

N	fibonacci(0)	fibonacci(1)
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3
5	3	5
6	5	8
7	8	13
8	13	21

풀이가 2가지가 나오는데 두 방법을 모두 보도록 하겠습니다.

 

첫번째 풀이

fibonacci(1)이 호출되는 숫자는 잘 생각해보면 1이 나와서 그 값들을 모두 더해야 피보나치 함수의 결과값이 됩니다.

따라서, 피보나치 재귀함수를 그대로 푸는 수와 동일하므로 이걸 DP로 표시한 것이 D[N] = D[N-1] + D[N-2]입니다.

(문제에 소개된 C++ 소스에서도 표시된 점화식입니다.)

  -> return fibonacci(n‐1) + fibonacci(n‐2);

 

fibonacci(0)을 자세히 보시면 D[0] = 1이면서 D[N] = D[N-1] + D[N-2]의 형태를 지닌 수열이라는 것을 알 수 있습니다.

따라서, fibonacci(1)을 D1이라고 정의하면 

D1[0] = 0

D1[1] = 1

D1[N] = D1[N-1] + D1[N-2] 입니다.

그리고 fibonacci(0)을 D0이라고 정의하면

D0[0] = 1

D0[1] = 1

D0[N] = D0[N-1] + D0[N-2] 으로 풀 수 있습니다.

 

두번째 풀이

위의 표를 다시 자세히 보면 fibonacci(0)과 fibonacci(1)에서 중복되는 패턴이 있다는 것을 알 수 있습니다.

N	fibonacci(0)	fibonacci(1)
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3
5	3	5
6	5	8
7	8	13
8	13	21

 

노란색 배경으로 표시해보면

D0[1] = D1[0]

D0[2] = D1[1]

와 같이 1칸씩 어긋나게 차이나는 것을 알 수 있습니다.

예를 들어 N이 5인 경우 

fibonacci(0)은 D0[5] = 3입니다.

fibonacci(1)은 D1[5] = 5이지만 D0와 비교하면 D0[6] 값과 동일합니다.

즉, D1[N] = D0[N+1]과 같습니다.

 

그러면 fibonacci(1)을 구하지 않고 fibonacci(0)을 구한 다음

D0[N]과 D0[N+1]을 출력해도 됩니다.

 

 

 

소스

위에서 구한 점화식을 이용하여 다이나믹 프로그래밍으로 구현하였습니다.

 

첫번째 소스

fibonacci(0)은 D0 배열로 선언하고

fibonacci(1)은 D1 배열로 선언하였습니다.

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

public class Main
{
	static int N;
	static long D0[] = new long[41];
	static long D1[] = new long[41];

	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String input = br.readLine();
		StringTokenizer st = new StringTokenizer(input);
		
		int T = Integer.valueOf(st.nextToken());
		
		for (int test_case = 0; test_case < T; test_case++)
		{
			input = br.readLine();
			st = new StringTokenizer(input);
			N = Integer.valueOf(st.nextToken());

			D0[0] = 1;
			D1[1] = 1;

			for (int i = 2; i <= N; i++)
			{
				D0[i] = D0[i-1] + D0[i-2];
				D1[i] = D1[i-1] + D1[i-2];
			}
			
			System.out.println(D0[N] + " " + D1[N]);
			
//			System.out.println(Arrays.toString(D0));
//			System.out.println(Arrays.toString(D1));
		}
	}
}

 

두번째 소스

fibanacci(0)을 D배열에 저장하고 출력할 때 D[N] D[N+1]로 하였습니다.

for문에서 N+1까지 구해야 한다는 점을 유의하시면 됩니다.

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

public class Main
{
	static int N;
	static long D[] = new long[42];

	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		StringTokenizer st = new StringTokenizer(input);
		
		int T = Integer.valueOf(st.nextToken());
		
		for (int test_case = 0; test_case < T; test_case++)
		{
			input = br.readLine();
			st = new StringTokenizer(input);
			N = Integer.valueOf(st.nextToken());
			
			D[0] = 1;

			for (int i = 2; i <= N+1; i++)
			{
				D[i] = D[i-1] + D[i-2];
			}
			
			System.out.println(D[N] + " " + D[N+1]);
			
//			System.out.println(Arrays.toString(D));
		}
	}
}