[C] 백준 1003번 (피보나치 함수)

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을 넣었을 때, 0과 1이 몇번씩 출력되는지를 구하면 되는 문제이다.

피보나치 함수는 재귀적으로 함수를 호출하게 되는데 그림으로 그려보면 다음과 같다.

예를 들어, 피보나치 수열의 3, 4, 5항의 계산은 이런식으로 이루어진다. 우리는 여기서 각 항에 0과 1의 개수가 몇개인지만 알면 정답을 맞힐 수 있다. 5항까지 그려봤으니 6항에는 0과 1이 몇개 있을지 생각해보자.
간단하다. 4항에 있는 0과 1의 개수 그리고 5항에 있는 0과 1의 개수를 더해주면 된다. 6항을 계산하는 방식은 다음과 같을테니 말이다.

4항과 5항을 계산한 것 위에 6을 달아주면 그게 피보나치 수열의 6번째 항을 계산한게 된다.

즉 n번째 항을 계산할 때 출력되는 0과 1의 개수는 n-1번째항을 계산할 때와 n-2번째 항을 계산할 때 출력되는 0과 1의 개수를 합한 것과 같다. 결국 피보나치 수열의 값을 출력하는게 이 문제의 전부이다.
fibonacci(0)일 때는 0의 개수가 1     1의 개수가 0
fibonacci(1)일 때는 0의 개수가 0     1의 개수가 1이다.
fibonacci(2)부터는 반복문으로 앞에 있는 두개의 항을 더해주면 된다. 0의 개수와 1의개수를 따로 계산하는 것만 주의하자.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int num0[41];
int num1[41];

int main(void) {	
	int t; scanf("%d", &t); 
	int n;
	num0[0] = 1, num1[0] = 0;
	num0[1] = 0, num1[1] = 1;	
	for (int i = 2; i <= 40; i++) {
		num0[i] = num0[i - 1] + num0[i - 2];
		num1[i] = num1[i - 1] + num1[i - 2];
	}
	while (t--) {
		scanf("%d", &n);	
		printf("%d %d\n", num0[n], num1[n]);
	}
	
	
	
}

num0에는 0의 개수를, num1에는 1의 개수를 저장한다.

이 문제에서 시간초과가 나온 사람들은 아마도 문제에서 주어진 피보나치 함수에 printf("1")을 할 때마다 특정 변수의 값을 +1 시키고, printf("0")을 할 때마다 또 특정 변수의 값을 +1 시키는 방식으로 했을 것이다. 문제에서 n은 최대 40이라고 했는데, 40을 넣어보면 정답으로 출력되는 숫자가 제법 크다. 그 짓을 테스트 케이스 한 번 돌릴때마다 해야하니 시간이 오래걸릴 수 밖에 없다. 한 번 계산된 것들을 그 다음번에 또 계산하는 게 아니라 한 번 계산할 때 배열에 저장해놓고 그 이후부터는 저장된 값을 가져와서 쓰기만 하면 된다.