글 읽기 - 시간초과를 해결하지 못하겠습니다..

physiqueloper 1년 전 0

대충 맞게 한것같은데 16프로에서 시간초과가 계속 발생하네요.. 뭐가 문제일까요??

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

public class Main {
	static int cnt1 = 0;
	static int cnt0 = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine());
		int[] answer0 = new int[41];
		int[] answer1 = new int[41];
		boolean[] ts = new boolean[41];
		String[] answer = new String[n];
		
		for (int i = 0; i < n; i++) {
			int t = Integer.parseInt(br.readLine());
			fibo(t, ts, answer0, answer1);
			ts[t] = true;
			answer0[t] = cnt0 ;
			answer1[t] = cnt1;
			answer[i] = cnt0+" "+cnt1;
			cnt0 = 0;
			cnt1 = 0;
		}
		for (String string : answer) {
			System.out.println(string);
		}
	}

	// 피보나치에서 f(0), f(1)이 몇 번 호출 되는지 count
	static void fibo(int n, boolean[] ts,int[] answer0, int[] answer1) {
		
		if(ts[n]== true) {
			cnt0 += answer0[n];
			cnt1 += answer1[n];
			return ;
		}
		if (n == 1) {
			cnt1++;
			return ;
		}
		if (n == 0) {
			cnt0++;
			return ;
		}
		fibo(n - 1, ts, answer0, answer1);
		fibo(n - 2, ts, answer0, answer1);
	}
}

hhs2003 1년 전 1

재귀적으로 구성하면 피보나치의 N번째 함수를 찾기 위해 2의 N승의 연산을 필요로 합니다.

N은 40까지 나올 수 있으므로, 2의 40승번의 연산은 시간초과를 하게 됩니다.

재귀적이 아닌, 이전에 계산한 값을 다음 계산에 이용하여, 동적계획법으로 코드를 구성하면, N번의 연산으로 끝낼 수 있습니다.

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

문제

문제

출처

ICPC

시간초과를 해결하지 못하겠습니다..

physiqueloper 1년 전 0

hhs2003 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말