글 읽기 - 2193번 질문입니다

hsyoon702 7년 전 0

시간 초과가 뜨는데 뭐가 잘못됐을까요?

완전 딱 피보나치문제여서 그렇게 풀었습니다.

답변 부탁드립니다.

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		int testcase = sc.nextInt();
		
		System.out.println(Fib(testcase));

	}
	public static int Fib(int testcase){
		if (testcase <= 1)
			return testcase;
		else 
            return Fib(testcase - 2) + Fib(testcase - 1);
	}
}

wakeupear1y 7년 전 0

피보나치를 재귀로 구하게 될 경우, 중복호출이 많아 O(2^n)시간이 걸리는데,

n이 90일때 1237940039285380274899124224 만큼걸립니다.

보시다시피 매우 큰 시간이기 때문에 시간초과에 걸린 것 같습니다.

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

문제

문제

출처

ICPC

2193번 질문입니다

hsyoon702 7년 전 0

wakeupear1y 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말