백준 1003번 피보나치 함수 JAVA

링크텍스트

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

public class Main {
    
    static Integer arr[][] = new Integer[41][2]; 
    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());
        
        arr[0][0]=1;
        arr[0][1]=0;
        arr[1][0]=0;
        arr[1][1]=1;

        for(int i=0;i<n;i++){
            int num = Integer.parseInt(br.readLine());
            fibonacci(num);
            sb.append(arr[num][0]+" "+ arr[num][1]+"\n");
        }
		System.out.print(sb);
    }
    public static Integer[] fibonacci(int n){
        
        if(arr[n][0]==null || arr[n][1]==null){
            arr[n][0]= fibonacci(n-1)[0]+fibonacci(n-2)[0];
            arr[n][1] = fibonacci(n-1)[1]+fibonacci(n-2)[1];
        }
        return arr[n];
    }
}

처음에는 dp를 사용하지않아 메모리 초과로 실패했다.

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

public class Main {

    static ArrayList<Integer> al = new ArrayList<>();
    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());

        for(int i=0;i<n;i++){
            int num = Integer.parseInt(br.readLine());
            int zero = 0;
            int one = 0;

            fibonacci(num);

            for(int nn: al){
                if(nn==0){
                    zero++;
                }else if(nn==1){
                    one++;
                }
            }
            sb.append(zero+" "+one+"\n");
            al.clear();
        }

        System.out.print(sb);
    }


    public static int fibonacci(int n){
        if(n==0){
            al.add(0);
            return 0;
        }else if(n==1){
            al.add(1);
            return 1;
        }else{
            return fibonacci(n-1)+fibonacci(n-2);
        }
    }
}

TopDown 코드

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

public class Main {
        static int n;
        static int [][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int t = Integer.parseInt(br.readLine());

        while(t-->0){
            int n = Integer.parseInt(br.readLine());

            dp = new int[n+1][2];

           
            for(int i=0;i<=n;i++){
                dp[i][0] = -1;
                dp[i][1] = -1;
            }

            int [] answer = TopDown(n);

            sb.append(answer[0]).append(" ").append(answer[1]).append("\n");
        }

        System.out.print(sb);
    }

    public static int [] TopDown(int n){
        if(n==0) return new int [] {1,0};
        else if(n==1) return new int [] {0,1};

        if(dp[n][0]!=-1) return dp[n];

        int [] a = TopDown(n-1);
        int [] b = TopDown(n-2);

        dp[n][0] = a[0]+b[0];
        dp[n][1] = a[1]+b[1];
        
        return dp[n];
    }
}