글 읽기 - 메모리 초과

tksgk7411 1년 전 0

메모리 초과가 나오는데 어디 수정을 해야 할지 잘 모르겠네요 ㅠㅠ

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int zero=0;
    static int one =0;

   public static  int fibo(int num){
        int [] dp= new int[num+1];
        if(num==0) {zero++; return 0;}
        else if(num==1){one++; return 1;}
        else if(dp[num]!=0){ return dp[num];
        }
        return dp[num] = fibo(num-1)+fibo(num-2);

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
         BufferedWriter bw =  new BufferedWriter(new OutputStreamWriter(System.out));

        int Num = Integer.parseInt(st.nextToken());
        int [] list = new int[Num];

        for (int i = 0; i <Num ; i++) {
          st = new StringTokenizer(br.readLine());
            list[i]= Integer.parseInt(st.nextToken());
        }

        for (int i : list) {
            fibo(i);
            bw.write(zero+" "+one+"\n");
            zero=0;
            one=0;
        }

        bw.flush();   //남아있는 데이터를 모두 출력시킴
        bw.close();   //스트림을 닫음
        br.close();    
    }
    }

semi0777 1년 전 0

이렇게쓰면 스택이 2^n-1개의 스택이 생성돼서 스택을 못버틸 거 같네요

f(n) = f(n-1) + f(n-2) = f(n-2)*2 + f(n-3) = ?

이걸 이용해보세요

tksgk7411 1년 전 0

댓글 감사합니다.

메모리제이션을 써도 스택이 2^n개가 생성되나요?

semi0777 1년 전 0

아하 메모리제이션을 쓰셨네요 그러면 호출스택자체는 확연히 줄겠지만 그래도 while을 쓰시는게 더 좋을거같아요

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

문제

문제

출처

ICPC

메모리 초과

tksgk7411 1년 전 0

semi0777 1년 전 0

tksgk7411 1년 전 0

semi0777 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말