글 읽기 - 시간초과 질문드립니다.

pjm6401 2년 전 0

자바로 문제 답을 작성하였는데, 처음에 시간초과가 되어서 전부 버퍼 리더, 스트링 빌더로 바꿨는데도 시간초과라고 나와서 어디에 문제가있는지 궁금해 올립니다.

import java.io.*;
public  class Main {
    public static int count[] ={0,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()); // testcase
        int a [] = new int [n];
        count = new int [2];
        for(int i =0; i<n; i++) {
            a[i] = Integer.parseInt(br.readLine());
            }
        for(int i=0; i<n; i++){
            fibo(a[i]);
            sb.append(count[0] + " "+count[1]+"\n");

            for(int k=0;k<2;k++){
                count[k] =0;
            }
        }
        System.out.println(sb.toString());
    }


    public static int fibo(int a){
        if(a==0){
            //System.out.print(0);
            count[0]+=1;
            return 0;
        }
        else if (a==1)
        {
            //System.out.print(1);
            count[1]+=1;
            return 1;
        }
        else{
            return fibo(a-2)+ fibo(a-1);
        }
    }
}

kvyft1234 2년 전 0

피보니치 수열의 0번째부터 39번째까지로 문제 조건에서 주어줬기 때문에

미리 39번째까지 계산한 결과를 배열에 넣어서

n번째 항을 구하기 위해 피보나치 함수에서 0을 호출한 횟수가 n-2번째 항과 동치이고 1을 호출한 횟수가 n-1번째 황과 동치였나 그래가지고

결과값으로 배열에서 저장해뒀던 (n-2)번째 항과 (n-1)번째 항만 반환하면 됩니다.

이러면 시간복잡도 O(1)로 나와요.

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

문제

문제

출처

ICPC

시간초과 질문드립니다.

pjm6401 2년 전 0

kvyft1234 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말