글 읽기 - 시간초과가 왜 나는지 모르겠습니다.

epic3905 2년 전 0

시간초과가 왜 나는지 모르겠습니다.

#include <stdio.h>
int zero, one = 0;

int fib(int _n)
{
	if (_n == 0)
	{
		zero++;
		return 0;
	}
	if (_n == 1)
	{
		one++;
		return 0;
	}
	return fib(_n - 1) + fib(_n - 2);
}

int main()
{
	int n;
	int t;
	scanf("%d", &t);
	for (int i = 0; i < t; i++)
	{
		scanf("%d" , &n);
		fib(n);
		printf("%d %d\n" , zero , one);
	}
}

0000000000 2년 전 0

이렇게 하시면 중복이 엄청나게 많이 발생하기 때문에 당연히 시간초과가 나게 됩니다. 메모이제이션을 해 주셔야 합니다.

sonjaewon 2년 전 0

Dynamic Programming 에 대해 공부해보는 것을 추천드립니다.

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

문제

문제

출처

ICPC

시간초과가 왜 나는지 모르겠습니다.

epic3905 2년 전 0

0000000000 2년 전 0

sonjaewon 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말