백준 1003 번 문제

정답

문제 풀이를 위해 구조체와 배열을 사용해 진행하도록 한다.

 

#include <iostream>
#include <stdlib.h>
using namespace std;
int memoryzero[41]={0};
int memoryone[41] ={0};
int fibonacci(int n){
    if(n==0){
     //cout<<"n==0"<<endl;
return 0;
}
else if(n==1){
//cout<<"n==1"<<endl;
return 0;
}
else if(memoryzero[n]==0&&memoryone[n]==0){
//cout<<"memoryzero[n]==0&&memoryone[n]==0"<<endl;
fibonacci(n-2);
fibonacci(n-1);

memoryzero[n]= memoryzero[n-1]+memoryzero[n-2];
memoryone[n]= memoryone[n-1]+memoryone[n-2];
return 0;
}
else
return 0;

}

int main(int argc, char * argv[]){
memoryzero[0]=1;
memoryone[1]=1;

int num=0;

cin >> num;
int *temp = (int*)malloc(sizeof(int) * num);

for(int i=0;i<num;i++){
cin >> temp[i];

fibonacci(temp[i]);
cout<<memoryzero[temp[i]] <<" "<< memoryone[temp[i]]<<endl;
}
free(temp);
return 0;
}

 

코드를 짧게 만드는것은 머리를 좀 깨우고 난 뒤에 진행하려한다.

현재는 코딩자체를 너무 오래간만에 진행하였기 때문에

머리를 말랑말랑하게 만드는것을 먼저 진행하도록 한다.

 

 

 

 

 

시간 초과로 인해 실패한풀이

 

#include <iostream>
#include <stdlib.h>
using namespace std;


int fibonacci(int n, int * zero, int * one){
    if (n == 0) {
        *zero = *zero + 1;
        return 0;
    } else if (n == 1) {
        *one = *one +1;
        return 1;
    } else {
        return fibonacci(n-1,  zero,  one) + fibonacci(n-2, zero, one);
    }
}
int main(int argc, char * argv[]){
int zero=0;
int one=0;
int num=0;

cin >> num;
int *temp = (int*)malloc(sizeof(int) * num);

for(int i=0;i<num;i++){
cin >> temp[i];
}

for(int i=0;i<num;i++){
zero=0;
one=0;
fibonacci(temp[i],&zero,&one);
cout <<endl << zero <<" " << one;
}

free(temp);
}

상단의 코드는 피보나치 수열을 계산하는 함수의 

중복된 계산 부분을 처리하지 못해 속도적인 면에서 느려

시간초과로 인해 실패한 풀이라고 볼 수 있다.