백준 1003 피보나치 함수 문제풀이와 해설

은근히 헷갈리는 문제이긴 했는데, 헤메다가 결국 풀이했습니다 :)

​

피보나치의 합계를 푸는거라면 좀 수월할텐데,

재귀호출에서 0과 1이 나오는 횟수를 풀라니 크레이에게는 좀 난해했습니다.

​

피보나치 수열에서 재귀호출로 계산할 때 0과 1이 연산에 들어가는 횟수인지

숫자가 클수록 기하급수적으로 늘어나더라구요.

​

이것 저것 고민하다가 인터넷 다른 분의 게시글도 참고하긴 했지만,

결국은 독자적으로 초고속으로 작동하도록 새로 만들었습니다.

​

long long 형 변수로 선언해서

60피보나치의 0과 1의 갯수까지도 계산할 수 있으며

( 79로 시도해봤었는데 숫자 범위 초과로 엉뚱한 숫자가 구해지더라구요.

혼란드린점 죄송합니다 )

60피보나치일 경우라도 연산시간은 10ms 이내인듯 합니다 :)

측정해보기는 귀찮아서 해보진 않았구요.

백준사이트는 최대값이 40인데 결과가 0ms 로 나오더라구요.

​

​

시간제한

0.25초

​

문제

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

​

예제입력

3

0

1

3

​

예제출력

1 0

0 1

1 2

​

크레이의 해설

피보나치 수열을 구하는 방법 중 가장 비효율적인 방법은

바로전단계와 전전단계의 숫자를 더해주는 것을 무한정 재귀 호출하는 방법입니다.

​

보통 피보나치 수열을 구하기 위해서는

통상적으로 맨 앞에 0 과 1을 써놓고, 3번째 숫자부터는 바로 앞의 2개의 숫자를 구하는 방법이 있습니다

처음에는 0 과 1을 써놓고

0 1

그 다음 칸에는 맨 뒤에 놓여진 2개의 숫자의 합을 적습니다.

0 + 1 = 1

그 다음 칸에 또 연속해서 맨 뒤에 놓여진 2개의 숫자의 합을 적는 것이지요

0 1 + 1 = 2

이 과정을 계속 반복하는 것이 바로 피보나치 수열입니다.

0 1 1 2 3 5 8 + 13 = 21 ...

위에서 21은 피보나치 몇번 수열일까요?

9번째이긴 하지만 8번 수열입니다. 피보나치 수열은 0번부터 시작하기 때문이지요 :)

​

이런 방식으로 피보나치 수열을 구하면 피보나치 수열은 금방 구해집니다.

​

하지만 본 문제는 피보나치 수열을 가장 비효율적으로 구하는 방법을 채택할 때의 최종 재귀호출이 되는 피보나치함수0번과 1번이 각각 몇번씩 호출되는지를 구하는 문제입니다.

​

한번 피보나치 6번 수열을 기준으로 들어볼까요?

피보나치 6번은 피보나치 5번 + 피보나치 4번입니다.

결과론적으로는 8 = 5 + 3 이지만, 피보나치 5번함수가 값이 5라는 사실과 피보나치 4번이 값이 3이라는 사실은 아직 알수가 없습니다.

​

다시 피보나치 5번 함수의 결과를 알기 위해 피보나치5번 = 피보나치4번 + 피보나치3번을 구합니다. 이 과정을 1또는 0이 확정될때까지 구하는 것입니다.

전체 연산 과정을 살펴보도록 할까요?

피보나치6번 이렇게 적으면 너무 기니까 P(6)으로 적어보도록 할까요?

​

P(6)=P(5)+P(4)

P(5)=P(4)+P(3)

P(4)=P(3)+P(2)

P(3)=P(2)+P(1)

P(2)=P(1)+P(0)

P(2)=P(1)+P(0)

P(3)=P(2)+P(1)

P(2)=P(1)+P(0)

P(4)=P(3)+P(2)

P(3)=P(2)+P(1)

P(2)=P(1)+P(0)

P(2)=P(1)+P(0)

​

빨간색으로 표시된 부분이 피보나치 0번, 1번이 사용되는 횟수인데

P(0)은 5번, P(1)은 8번 사용되었지요?

원래 간단한 계산인데 매우 복잡해졌습니다.

​

이 문제의 목적은 이 횟수를 구하는 것입니다.

그러면 그냥 원래의 재귀함수를 이용해서 세면서 구하면 되지 않느냐는 생각이 있을 수 있지만,

결론을 말씀드리면 그 방법으로는 문제를 해결할 수 없습니다.

왜냐하면 피보나치 숫자가 커지면 커질수록 횟수가 기하급수적으로 불어나기 때문입니다.

​

문제에서 제시된 최대값 피보나치40의 경우

0은 63,245,986, 1은 102,334,155 번 사용됩니다.

시도해본 결과 본 문제의 제한시간 0.25내에 통과해야 하는데 통과할 수 없습니다.

​

그렇다면 어떤 방법이 있을까요?

가장 효율적인 방법은 반복적인 계산을 없애는 것입니다.

피보나치에서 사용되었던 0과 1의 사용횟수를 저장했다가 활용하는 방법이지요.

​

그러려면 각 결과값을 저장할 변수를 먼저 전역변수로 선언해야 합니다.

원래 41이면 되지만 크레이는 테스트할게 있어서 101까지 선언했지요 :)

 

// 0~40번까지 0과 1과 합계를 담을 변수 정의
long countarr_0[41];
long countarr_1[41];
long sumarr[41];

테스트 케이스를 입력받아 반복하는 부분은 아주 기초단계이므로 넘어가도록 하겠습니다 :)

​

제일 먼저 시작하기 전에 전역변수를 모두 0으로 초기화해줍니다.

 

		for(int i=0;i<=40;++i)
		{
			countarr_0[i]=0;
			countarr_1[i]=0;
			sumarr[i]=0;
		}

다음 단계로 입력받은 숫자의 피보나치함수를 바로 호출하는 것이 아니라,

0부터 시작해서 1씩 숫자를 올려가며 피보나치 함수를 호출합니다.

		for(int i=0;i<=n;++i)
			fibonacci(i, i);

피보나치 함수는 이렇게 생겼습니다.

어떤 결과가 나올까요?

 

// 피보나치 함수에 현재 구하려는 수를 함께 넘긴다
int fibonacci(int n, int base) 
{
	if(sumarr[n]>0)return sumarr[n];
    if (n == 0) {
		countarr_0[base]++;
        return 0;
    }
    else if (n == 1) {
		countarr_1[base]++;
        return 1;
    }
    else {
		int sum1, sum2;
		if(sumarr[n-1]>0)
		{
			sum1=sumarr[n-1];
			countarr_0[base]+=countarr_0[n-1];
			countarr_1[base]+=countarr_1[n-1];
		}
		else sum1=fibonacci(n-1, base);

		if(sumarr[n-2]>0)
		{
			sum2=sumarr[n-2];
			countarr_0[base]+=countarr_0[n-2];
			countarr_1[base]+=countarr_1[n-2];
		}
		else sum2=fibonacci(n-2, base);

		//printf("%d = %d + %d\n", n, n-1, n-2);
		return sumarr[base] = sum1 + sum2;
    }
}

피보나치 함수를 호출하는 전체횟수가 매우 단축되는데요.

기하급수적으로 늘어나지 않고 n + 3번만 호출됩니다.

​

0부터 시작해볼까요? 먼저 피보나치 0을 구합니다.

fibonacci(0, 0);

그러면 함수의 흐름에 따라 P(0)이 한번 사용되었다고 0번 배열에 저장하고 끝납니다.

 

    if (n == 0) {
		countarr_0[base]++;
        return 0;
    }

다음으로 피보나치 1을 구합니다. 0과 비슷한 방식으로 P(1)이 한번 사용되었다는 표식으로 1번 배열에 저장하고 끝납니다.

 

    else if (n == 1) {
		countarr_1[base]++;
        return 1;
    }

다음으로 피보나치 2를 구하는데요.

이 때부터는 좀 생각을 해야 합니다.

n과 base 라는 변수 2개가 주어지는 이유가 있기 때문입니다.

 

fibonacci(int n, int base) 

n은 현재의 재귀호출되는 피보나치 수열번호이고,

base는 처음의 피보나치 수열번호입니다.

​

이를테면 P(2)를 구할때는

다시 P(1), P(0)을 호출하게 되는데,

P(1) 과 P(0) 을 호출할 때 n값은 각각 1과 0이지만,

base 값은 처음 숫자인 2인 것이지요.

그러면 피보나치 함수 내에서는 앞에서 처리되었던 동일한 코드를 거치지만,

다른 결과를 낳습니다.

각각 countarr_0 배열변수와 countarr_1 배열변수에서

0, 1번 배열이 아닌 2번 배열에 사용횟수를 더해주게 됩니다.

 

    if (n == 0) {
		countarr_0[base]++;
        return 0;
    }
    else if (n == 1) {
		countarr_1[base]++;
        return 1;
    }

그리고 추가적으로 P(1) + P(0)계산이 끝난 다음,

sumarr[2] 번 변수에 합계값을 저장합니다.

​

합계를 구하는 부분은 사실 필요없지만,

이미 0과 1의 갯수를 세었다는 표시로 저장해놓는 것이지요.

return sumarr[base] = sum1 + sum2;

이제 다시 피보나치 3번을 구해볼까요?

P(3) = P(2) + P(1) 입니다.

P(1) 은 바로 전과 똑같지만

P(2) 는 좀 다릅니다. 이 때부터 고속 산출 방식이 적용되는데요.

이미 P(2)의 0과 1의 사용횟수와 합계는 계산이 끝났기 때문에

계산이 끝난 값을 사용하면 됩니다.

n의 값은 현재 3입니다. P(2) 의 합계값인 sumarr[n-1] 변수에 합계가 저장되어 있습니다.

그러니 0과 1의 사용횟수도 저장된 횟수를 불러다가 3번 배열에 저장해주는 것이지요.

		if(sumarr[n-1]>0)
		{
			sum1=sumarr[n-1];
			countarr_0[base]+=countarr_0[n-1];
			countarr_1[base]+=countarr_1[n-1];
		}

피보나치 3번의 합계 또한 산출했다고 저장해놓습니다.

 

return sumarr[base] = sum1 + sum2;

피보나치 4번에서는 어떨까요?

P(3) + P(2) 인데, 이번에는 2개 모두 이미 계산이 끝난 상황이기 때문에

위와 동일한 로직에 따라,

P(3)의 0과 1의 사용횟수, P(2) 의 0과 1의 사용횟수를 더해서 4번째 사용횟수와 합계 배열에 저장합니다.

​

이 과정을 목적이 되는 숫자까지 계속 반복하는 것입니다.

결론을 말씀드리면 재귀호출로 구할 수밖에 없었던 0과 1의 사용횟수, 합계를 전역변수에 저장하여 반복계산을 하지 않음으로서 재귀호출과정이 현저하게 줄어드는 방식입니다.

​

꽤 머리를 굴려야 해서 이론적인 부분의 설명은 이 것으로 마치고,

실제 구현된 부분은 아래 소스 코드를 통해서 이해해 주시기 바랍니다.

​

이런 유형의 문제풀이는 여러번 봐서 눈에 익히고 한번 직접 풀어보셔야

이해가 가능하니 한번에 이해가 안된다고 낙담하지 마세요 :)

​

소스

#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;

// 0~40번까지 0과 1과 합계를 담을 변수 정의
long long countarr_0[101];
long long countarr_1[101];
long long sumarr[101];

// 피보나치 함수에 현재 구하려는 수를 함께 넘긴다
int fibonacci(int n, int base) 
{
	if(sumarr[n]>0)return sumarr[n];
    if (n == 0) {
		countarr_0[base]++;
        return 0;
    }
    else if (n == 1) {
		countarr_1[base]++;
        return 1;
    }
    else {
		int sum1, sum2;
		if(sumarr[n-1]>0)
		{
			sum1=sumarr[n-1];
			countarr_0[base]+=countarr_0[n-1];
			countarr_1[base]+=countarr_1[n-1];
		}
		else sum1=fibonacci(n-1, base);

		if(sumarr[n-2]>0)
		{
			sum2=sumarr[n-2];
			countarr_0[base]+=countarr_0[n-2];
			countarr_1[base]+=countarr_1[n-2];
		}
		else sum2=fibonacci(n-2, base);

		//printf("%d = %d + %d\n", n, n-1, n-2);
		return sumarr[base] = sum1 + sum2;
    }
}

void Result()
{
	int t;

	scanf("%d", &t);
	while (t--)
	{
		int n;
		scanf("%d", &n);
		for(int i=0;i<=40;++i)
		{
			countarr_0[i]=0;
			countarr_1[i]=0;
			sumarr[i]=0;
		}
		for(int i=0;i<=n;++i)
			fibonacci(i, i);

		printf("%lld %lld\n", 
			countarr_0[n],
			countarr_1[n]);
	}
}
int main()
{
       Result();
      return 0;
}