글 읽기 - 시간초과라는데 어느부분을 수정해줘야 할까요 ㅠㅠ

jyb1346 7년 전 0

이것이 제 코드인데 시간초과라고 나오는데 제 코드가 아예 틀린건지 맞는건지도

알수도 없네요 ㅠㅠ 어디서 시간초과가 나오는 걸까요

#include<iostream>
using namespace std;

int fibonacci(int n) 
{
	if (n == 0)
	{
		return 0;
	}
	else if (n == 1)
	{
		return 1;
	}
	else
	{
		return fibonacci(n - 1) + fibonacci(n - 2);
		
	}
}

int main()
{
	int num;
	int testcase;
	cin >> num;

	for (int i = 0; i < num; i++)
	{
		cin >> testcase;
		if (testcase == 0)
		{
			cout << "1 0" << "\n";
		}
		else
		{
			cout << fibonacci(testcase - 1) << " ";
			cout << fibonacci(testcase) << "\n";
		}
	}
	return 0;
}

sksdong1 7년 전 0

답이 출력되는 원리는 아신거 같은데

피보나치를 dp를 이용해서 구해보세요.

allkanet72 7년 전 0

다이나믹 프로그래밍으로 풀어야합니다.

단순 함수 호출로만 풀면 매우매우 비효율입니다.

피보나치의 원리를 아시면 수가 커질수록 반복횟수도 지수적으로 커짐을 알 수있습니다.

jyb1346 7년 전 0

아 감사합니다 좀 찾아보니 이런류의 문제는 재귀적으로 접근하면 너무많이 시간이 걸리는군요

다이나믹 프로그래밍이란걸 새로 배워서 좋습니다

allkanet72 7년 전 0

운영자이신 백준님이 유투브에 다이나믹에 대해서 강의하신거 있습니다.

1번 문제가 피보나치인데 이해하는데 많은 도움 되실거에요

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

문제

문제

출처

ICPC

시간초과라는데 어느부분을 수정해줘야 할까요 ㅠㅠ

jyb1346 7년 전 0

sksdong1 7년 전 0

allkanet72 7년 전 0

jyb1346 7년 전 0

allkanet72 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말