백준 1003

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

실패한 코드 :

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int a, b;

int fibonacci(int N) {
	if (N == 0) {
		a++;
		return 0;
	}
	if (N == 1) {
		b++;
		return 1;
	}
	return fibonacci(N - 1) + fibonacci(N - 2);
}

int main() {
	int T, N;
	scanf("%d", &T);
	for (int i = 0; i < T;i++) {
		a = 0, b = 0;
		scanf("%d", &N);
		fibonacci(N);
		printf("%d %d\n", a, b);
	}
}

시간 초과가 뜬다..!
재귀함수라 그런지 실행 속도가 넘나 느린것..

다른 방법으로 출력되는 a,b 를 구해야 했다.
구글링하니까 이런 방법으로 하더라.. 학교에서 피보나치수열 코드로 짜는건 배웠던 것 같은데 이번에 확실히 기억해둘것!!

성공한 코드 :

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

void fibonacci(int N) {
	int a = 0, b = 1, c;
	if (N == 0) {
		printf("1 0\n");
		return 0;
	}
	if (N == 1) {
		printf("0 1\n");
		return 0;
	}
	for (int i = 1; i < N; i++) {
		c = a + b;
		a = b;
		b = c;
	}
	printf("%d %d\n",a,b);
}

int main() {
	int T, N;
	scanf("%d", &T);
	for (int i = 0; i < T;i++) {
		scanf("%d", &N);
		fibonacci(N);
	}
}