[백준]1003

1. 그냥 재귀적 으로 풀기 --> 시간 초과 많이 됨.

 

#include<stdio.h>
int zero, one;
int fibonacci(int n){
	if(n == 0){
		zero++;
		return 0;
	}else if(n == 1){
		one++;
		return 1;
	} else{
		return fibonacci(n-1) + fibonacci(n-2);
	}
}

 int main(){
 	
	int i,j,testc;
	scanf("%d",&testc);
	for(j=0;j<testc;j++){
	zero = 0;
 	one = 0;
	scanf("%d",&i);
	fibonacci(i);
	printf("0 : %d, 1:%d\n",zero,one);
	}
	return 0;
}

 

 

2. 메모제이션 방법으로 시간 줄이기

 

memo[n] 의 1의 갯수는 m[n-1]에서의 0과 1의 갯수를 더한것이다.

                0의 갯수는 m[n-2]의 결과를 가져온것이다.

#include<stdio.h>
int memo[30]={1,1};

int fibonacci(int n){
	if(n==0) return memo[n];
	 else if(n ==1) memo[n];
	 else{
		memo[n] = fibonacci(n-1) + fibonacci(n-2);
		return memo[n];
	}
}

 int main(){
 	
	int i,j,testc;
	scanf("%d",&testc);
	for(j=0;j<testc;j++){
	scanf("%d",&i);
	fibonacci(i);
	if(i==0) printf("0 : 1, 1:0\n");
    else if(i==1) printf("0 : 0, 1:1\n");
	else{
	printf("0 : %d, 1:%d\n",memo[i-2],memo[i-1]);
	}
	}
	return 0;
}

 

                                                                      <실행결과>