백준 #1003 피보나치 함수

이 문제는 6개월전에 백준 문제들을 본격적으로 풀면서 풀었던 문제입니다.  난이도는 Silver III 문제입니다.

 

레오나르도 피보나치(이탈리아 수학자)

 

피보나치 함수는 아주 간단한 구조를 가지고 있는데, 다양한 성질 등이 발견되면서 자주 거론되는 수열입니다.  C/C++ 언어를 배울 때에는 재귀함수(자기호출함수)의 개념을 익히는 데에 하노이 타워와 자주 거론됩니다.

 

이 문제는 정답률이 높은 편은 아닙니다.  아마 초기문제여서 그럴 수도 있겠네요.

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

1003번: 피보나치 함수

 

피보나치 수열은 초기화 값에 따라서 수열이 조금씩 틀려지는데요.

fib(0) = 0, fib(1) = 1 인 경우가 가장 일반적입니다.

 

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);
    }
}

 

이 코드에 의해서 출력되는 문자열은 어떻게 될까요?  몇개만 해보면요.

 

 

n	output	zero count	one count
0	0	1	0
1	1	0	1
2	10	1	1
3	101	1	2
4	10110	2	3
5	10110101	3	5

 

문제에서 요구하는 0의 갯수와 1의 갯수가 또 피보나치 수열을 이루고 있음을 알 수 있습니다.

이는 초기값이 0, 1 로 되어 있느냐 1, 0 으로 되어 있느냐의 차이이지, 피보나치 점화식을 그대로 가져가기 때문입니다.

 

n항까지의 피보나치 수열을 구한 다음, n번째 항이 1의 갯수, n-1번째 항이 0의 갯수가 됩니다.

 

소스는 참고용으로 봐주세요.

 

//------------------------------------------------------------------------------
//	baekjoon #1003 - Fibonacci
//		- by Aubrey Choi
//		- created at 2019-05-17
//------------------------------------------------------------------------------
#include <stdio.h>

int main()
{
	int t, n, f[42];
	f[0]=1, f[1]=0;
	for(int i=2;i<=41;i++) f[i]=f[i-1]+f[i-2];
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d", &n);
		printf("%d %d\n", f[n], f[n+1]);
	}
	return 0;
}