글 읽기 - 시간초과 해결방법

quf9484 5년 전 1

아래와 같이 코드를 구현하였는데 시간초과가 납니다.

코드를 구현하기 전에 코드가 시간초과가 날 것 같은지 아닌지 판단하는 방법이 있을까요??

#include <stdio.h>
#include <time.h>

int Fibo(int n)
{
	int sum = 0;
	
	if(n > 2){
		sum = Fibo(n-1) + Fibo(n-2);
	}
	else{
		return 1;
	}
	
	return sum;
}
int main()
{
	//clock_t start = clock();
    
	int n;
	scanf("%d", &n);
	
	printf("%d", Fibo(n));
 
   // printf("\n%0.5f\n",(float)(clock() - start)/CLOCKS_PER_SEC);


}

eric00513 5년 전 1

배열에 그 값을 저장하면 시간초과를 해결할 수 있습니다.

예시 코드는 아래와 같습니다. 틀릴수도 있으니까 참고만 하세요.

#include <stdio.h>

int a[91];

int Fibo(int n)
{
	int sum = 0;
	
	if(a[n] != 0) return a[n];
	else{
    	if(n > 2){
    		sum = Fibo(n-1) + Fibo(n-2);
    	}
    	else{
    		return 1;
    	}
	}
	
	return a[n] = sum;
}

int main()
{  
	int n;
	
	scanf("%d", &n);
	
	printf("%d", Fibo(n));
    return 0;
}

아 맞다 시간초과가 날지 안날지 계산해 보는 방법이 있습니다. 컴퓨터는 대략 1초에 1억번의 계산을 합니다. 그래서 반복문이나 재귀가 1억번이 넘어가면 시간초과가 나는 것입니다. 위의 피보나치 수 2 문제에서 n이 최대 90개이기 때문에 재귀는 약 2^90번 돌아갑니다. 2^31>21억인데, 컴퓨터는 절대 1초만에 문제를 해결할 수 없습니다. (일반적으로 단순한 재귀를 사용할 때)

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

문제

문제

출처

ICPC

시간초과 해결방법

quf9484 5년 전 1

jh05013 5년 전 1

eric00513 5년 전 1

eric00513 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말