[JAVA] 백준, 1003번 피보나치 함수

https://www.acmicpc.net/problem/1003

 

 

기존 피보나치 함수

https://www.acmicpc.net/problem/10870

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        Integer[] dp = new Integer[21];
        System.out.println(fibonacci(n, dp));
    }

    static int fibonacci(int n, Integer[] dp) {
        dp[0] = 0;
        dp[1] = 1;

        if (dp[n] == null) {
            dp[n] = fibonacci(n - 1, dp) + fibonacci(n - 2, dp);
        }

        return dp[n];
    }
}

 

코드

시간 제한이 걸려있기 때문에 메모이제이션을 사용하지 않으면 시간초과가 발생한다.

import java.io.*;

public class Main {

    static int[][] dp;

    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());
            dp = new int[41][];
            for (int j = 0; j < 41; j++) {
                dp[j] = new int[]{-1, -1};
            }
            
            // 초기값 세팅
            // 숫자가 0일 때, 0을 1번 출력, 1을 0번 출력
            // 숫자가 1일 때, 0을 0번 출력, 1을 1번 출력
            dp[0][0] = 1;
            dp[0][1] = 0;
            dp[1][0] = 0;
            dp[1][1] = 1;

            int[] result = fibonacci(num);
            sb.append(result[0] + " " + result[1] + "\n");
        }

        System.out.println(sb);
    }

    static int[] fibonacci(int n) {
        /**
         * ex) n == 3
         * dp[3][0] : 숫자가 3일 때, 0을 출력하는 횟수
         * dp[3][1] : 숫자가 3일 때, 1을 출력하는 횟수
         * 기존 피보나치 구현 : if(n == 0) return 0 
                            if(n == 1) return 1     
                            else dp[n] = fibonacci(n - 2) + fibonacci(n - 1)
         */
        if (dp[n][0] == -1 || dp[n][1] == -1) {
            dp[n][0] = fibonacci(n - 2)[0] + fibonacci(n - 1)[0];
            dp[n][1] = fibonacci(n - 2)[1] + fibonacci(n - 1)[1];
        }
        return dp[n];
    }
}