글 읽기 - 1003번 시간 초과 왜일까요?

tndus3053 9년 전 0

이거 시간 초과 왜 나나요?

#include <iostream>
using namespace std;
int fibo0(int n) {
    
    if (n==0) 
    return 1;
    else if (n==1) 
    return 0;
        else {
        int i;
        i=fibo0(n-1)+fibo0(n-2);
    return i;
    }
}

int fibo1(int n){
    if(n==0)
        return 0;
    else if(n==1)
        return 1;
        else{
        int i;
        i=fibo1(n-1)+fibo1(n-2);
        return i;
    }
}
int main(){
    int T;
    cin>>T;
    for(int i=0;i<T;i++){
    int a;
    cin>>a;
    cout<<fibo0(a)<<" "<<fibo1(a)<<endl;
    
    }
}

yukariko 9년 전 1

직접 계산해 보시면 아시겠지만

n이 10만 되도

fibo(0) , fibo(1) 을 호출 하는 갯수가 기하급수적으로 늘어나게 됩니다.

저 fibo0 함수를 호출하는대에도 매우 아슬아슬 할탠데 fibo1까지 호출하면 바로 시간 초과가 나겠죠.

tndus3053 9년 전 0

아 그렇군요. 감사합니다 ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1003번 시간 초과 왜일까요?

tndus3053 9년 전 0

yukariko 9년 전 1

tndus3053 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말