백준 1003번 피보나치 함수

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

재귀함수의 이해도를 높이기에 좋은 문제이다.

fibonacci(N) 은 fibonacci(N- 1)과 fibonacci(N - 2)를 리턴하므로
0과 1이 출력되는 개수 역시 피보나치 수열이다.

(단, 0 을 제외)

#include <stdio.h>

int main()
{
	int i, T, N;
	int array[41];
	array[0] = 0;
	array[1] = 1;
	for (i = 2; i <= 40; i++)
	{
		array[i] = array[i - 1] + array[i - 2];
	}
	scanf("%d", &T);
	for (i = 0; i < T; i++)
	{
		scanf("%d", &N);
		if (N == 0) printf("1 0\n");
		else
		{
			printf("%d %d\n", array[N - 1], array[N]);
		}
	}
	return 0;
}

다른 사람 코드

wookjae님의 코드

https://www.acmicpc.net/source/20887233

main(n,a,i,f1,f2,f3){
scanf("%d",&n);
while(n--){
	scanf("%d",&a);
	f2=0,f1=f3=1; // a가 0 일 때 1,0을 출력하기 위하여
	for(i=0;i<a;++i){
		f1=f2,f2=f3; // a가 1 일 때는 0 1 을 출력
		f3=f1+f2; // 각각이 피보나치 수열이고 순서가 하나 차이나는 걸 이용한 좋은 풀이다...
        다만 테스트 케이스가 많아질수록 내 코드가 시간이 더 적게 걸릴 것이다.
        f3는 f1과 f2를 더한 것
        즉, 피보나치 수열의 가장 마지막항 (출력해야되는 것 바로 이후 항)
        다음 반복문에서 f1은 f2의 값을 f2는 f3의 값을 가져오면서 f1은 직전 f3보다 한단계 전, f2는 직전 f3와 같은 값을 가지게 된다.
        
        처음에 0은 저렇게 예외 출력 가능한 이유는 처음의 f1인 1은 이 다음에 f2로 덮어씌워지기 때문이다.
	}
	printf("%d %d\n",f1,f2);
}
}

내가 욱재님의 알고리즘으로 짜본 코드

#include <stdio.h>

int main()
{
	int i, j, n, T, f1, f2, f3;
	scanf("%d", &T);
	for (i = 0; i < T; i++)
	{
		scanf("%d", &n);
		f1 = 1;
		f2 = 0;
		f3 = 1;
		for (j = 0; j < n; j++)
		{
			f1 = f2;
			f2 = f3;
			f3 = f1 + f2;
            //n = 0 일 때 1 0 으로 맞게 출력되고 n = 1일 때 0 1 로 맞게 출력된다. 그럼 이후는 피보나치 수열이 이어지도록 하였으므로 당연히 맞다.
            원리를 좀더 가시적으로 표현해보자면
            f1 f2는 0을 제외하고 피보나치 수열의 일부분
            f3 = f1 + f2이므로 당연히 피보나치 수열의 다음항
            즉, f1 f2 f3는 피보나치 수열의 일부분이고 출력은 f1 f2까지만!
		}
		printf("%d %d\n", f1, f2);
	}
	return 0;
}