글 읽기 - [C++] 왜 시간초과가 발생하는 걸까요?

kth991118 4년 전 0

재귀함수로 linear한 시간이 소요될 수 있게 작성한 것 같은데 99%에서 시간초과가 발생해

똑같은 알고리즘을 for문으로 구현하여서 맞았습니다.

혹시 재귀함수로 구현한 부분중에 어떤 부분이 시간초과를 발생시키는지 여쭙고 싶습니다ㅠ

#include <iostream>

using namespace std;

void fibonacci(long long int fn_1, long long int fn_2, int k)
{
    if(k==1)
    {
        cout<<fn_1+fn_2<<"\n";
    }
    else{
        fibonacci(fn_1+fn_2, fn_1, k-1);
    }
    
    return;
}

int main(int argc, const char * argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int k;
    
    long long int temp;
    long long int fibo[2]={0, 1};
    
    cin>>k;
    
    if(k==1)
    {
        cout<<k<<"\n";
        
        return 0;
    }
    
    //fibonacci(1, 0, k-1);
    
    for(int i=0; i<k-1; i++)
    {
        temp=fibo[0]+fibo[1];
        fibo[0]=fibo[1];
        fibo[1]=temp;
    }
    
    cout<<fibo[1]<<"\n";
    
    return 0;
}

rhdqor213 4년 전 0

k가 1이면 k를 출력하고, 그렇지 않으면 피보나치 함수를 실행시켜야 하니 else를 붙여주셔야 합니다.

kth991118 4년 전 1

k가 1이 아니라면 if문에 걸리지 않고 다음 문장을 실행하므로 굳이 else를 붙일 필요는 없습니다.

아래와 같은 형태로 제출했을 때 99%에서 시간초과가 발생하였는데 오늘 다시 제출해보니 맞았다는 결과가 나왔습니다.

#include <iostream>

using namespace std;

void fibonacci(long long int fn_1, long long int fn_2, int k)
{
    if(k==1)
    {
        cout<<fn_1+fn_2<<"\n";
    }
    else{
        fibonacci(fn_1+fn_2, fn_1, k-1);
    }
    
    return;
}

int main(int argc, const char * argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int k;
    
    cin>>k;
    
    if(k==1)
    {
        cout<<k<<"\n";
        
        return 0;
    }
    
    fibonacci(1, 0, k-1);
    
    return 0;
}

rhdqor213 4년 전 1

게시물엔 틀렸던 코드를 그대로 올려주셔야 합니다.

제출 결과를 다시 보시면 시간초과가 나셨던 코드는 if(k == 1) 안에 return 문이 없습니다.

그래서 프로그램이 종료되지 않고 fibonacci(1, 0, 0)이 실행되어 피보나치 함수가 무한 루프를 돌게 되는 것을 막기 위해 else를 달아주라고 한거였구요.

게시물의 코드가 아니라 작성자 님이 제출해주신 코드를 보고 답변을 달아서 혼란을 드린 점 죄송합니다.

kth991118 4년 전 0

죄송합니다 게시하는 과정에서 수정한 코드를 올린 것 같습니다!ㅠ

감사합니다^^

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

문제

문제

출처

ICPC

[C++] 왜 시간초과가 발생하는 걸까요?

kth991118 4년 전 0

rhdqor213 4년 전 0

kth991118 4년 전 1

rhdqor213 4년 전 1

kth991118 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말