글 읽기 - [1788_피보나치수의 확장] 시간초과를 해결하고싶습니다.

danseryu 3년 전 0

양수피보나치와 음수피보나치의 차이가 해당 수가 짝수,홀수인지에 따라 음수냐양수냐 차이라는 것을 발견하여

해당 문제의 출력에서 절대값에 1,000,000,000을 나누게되므로

결국 음수피보나치가 필요없다고 생각이되어

양수 피보나치메소드를 만들어 결과에 해당 수를 나누는 알고리즘을 이용했습니다.

다른분들의 코드를 참고해보니 양수피보나치메소드를 이용하는분들을 찾지못해서

혹시 해당 코드로하게되면 시간초과가 무조건 나게 되나해서 질문을 남깁니다.

해당 코드로 시간초과가 안날수있는 방법이 있을까요?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int number = Integer.parseInt(br.readLine());

		int result = 0;

		if(number == 0) {
			System.out.println(0);
			System.out.println(fibo(0));
		}

		else if(number > 0)		
			System.out.println(1);	
		
		else if(number < 0) {
			System.out.println(-1);
			number = -number;
		}
		
		
		result = fibo(number);

		
		System.out.println((result%1000000000));
	}

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

}

ehdrmsl2001 3년 전 0

피보나치 수를 dp로 구하시면 됩니다.

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

문제

문제

출처

ICPC

[1788_피보나치수의 확장] 시간초과를 해결하고싶습니다.

danseryu 3년 전 0

ehdrmsl2001 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말