[백준/C] 1003번: 피보나치 함수

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

1003번: 피보나치 함수

---

 

 

---

 

문제 분석

피보나치수열을 순서대로 풀어서 fibonacci(1)과 fibonacci(0)이 호출되는 횟수를 구하는 문제이다.

 

처음 시도했던 코드

#include <stdio.h>
int a=0, b=0;

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

int main(){
	int t;
	scanf("%d", &t);
	
	while(t--){
		int n;
		scanf("%d", &n);
		
		fibonacci(n);
		printf("%d %d\n", a, b);
		a=0;
		b=0;
	}
}

코드 분석

단순하게 수를 입력 받은 후 그 수를 분해해 fibonacci(1)과 fibonacci(0)의 횟수를 누적시켜 출력을 하려고 했다.

하지만 이 코드로는 시간 초과가 되는 것을 확인했다.

이유는 분해를 할 때마다 피보나치 함수를 끝까지 분해해 누적했기 때문에 러닝 타임이 길었다고 생각한다.

 

코드 진행 방향

그 후 문제에 대해 다시 생각하여 작은 수부터 누적하는 방법을 사용하기로 하였다.

fibonacci(0)일 경우는 1 0이 출력되고 fibonacci(1)일 경우는 0 1이 출력된다.

fibonacci(2)일 경우는 fibonacci(1)과 fibonacci(0)의 값의 합인 1 1이 출력된다.

 

이를 2차원 배열을 통해 값을 누적시켜 저장하여 N을 입력하였을 경우

fibonacci(N)은 fibonacci(N-1)과 fibonacci(N-2)의 값만을 구해 시간을 줄이는 방법을 선택했다.

 

---

 

코드

#include <stdio.h>
int main(){
	int t;
	scanf("%d", &t);
	
	int fibo[41][2];
	fibo[0][0]=1;
	fibo[0][1]=0;
	fibo[1][0]=0;
	fibo[1][1]=1;
	
	for(int i=2; i<41; i++){
		fibo[i][0]=fibo[i-1][0]+fibo[i-2][0];
		fibo[i][1]=fibo[i-1][1]+fibo[i-2][1];
	}
	
	while(t--){
		int n;
		scanf("%d", &n);
		
		printf("%d %d\n", fibo[n][0], fibo[n][1]);
	}
}