글 읽기 - 자꾸 시간초과된다고 하네여 ..

quswotmd5 9년 전 0

전역변수를 사용하지 않고 문제를 풀고 싶었는데

자꾸 시간초과가 뜨네요....

아래 소스코드에서 어떻게 수정을 해야 시간초과가 안 뜰까요?

그리고 putty로 하면 출력이 제대로 나오는데 테스트를 하면 출력이 제대로 안나와요

이거 시간초과때문인건가여?

도와주세요ㅠ..

#include <stdio.h>



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 tc,i;
    int num,zero,one;
    
    scanf("%d",&tc);
    for(i=0;i<tc;i++)
    {
        
   		zero = 0;
    	one = 0;
        scanf("%d",&num);
        fibonacci(num,&zero,&one);
        printf("%d %d\n",zero,one);
    }
   
    return 0;
}

yukariko 9년 전 1

원래 위 같이 재귀로 풀면 시간이 매우 아슬아슬하게 걸리게 되는데

전역변수를 안쓰고 포인터로 넘기니 시간이 넘어가버리게 됩니다.

재귀 말고 다른 방법으로 푸는것이 좋을것 같네요.

kium100 9년 전 0

Google에 Dynamic Programming 검색해보세요

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

문제

문제

출처

ICPC

자꾸 시간초과된다고 하네여 ..

quswotmd5 9년 전 0

yukariko 9년 전 1

kium100 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말