백준 1003번 자바 : 피보나치 함수

분류

• 다이나믹 프로그래밍

반복문(Bottom-Up)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main { 

    static int[][] dp = new int[45][2];
    public static void main(String[] args) throws IOException {
        // dp 채우기
        dp[0][0] = 1;
        dp[0][1] = 0;
        dp[1][0] = 0;
        dp[1][1] = 1;
        for(int i=2; i<dp.length; i++) {
            dp[i][0] = dp[i-1][0] + dp[i-2][0];
            dp[i][1] = dp[i-1][1] + dp[i-2][1];
        }

        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T-->0) {
            int N = sc.nextInt();
            System.out.println(dp[N][0] + " " + dp[N][1]);
        }
    }

}

재귀(Top-down)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main { 

    static Integer[][] dp = new Integer[45][2];
    public static void main(String[] args) throws IOException {
        dp[0][0] = 1;
        dp[0][1] = 0;
        dp[1][0] = 0;
        dp[1][1] = 1;

        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T-->0) {
            int N = sc.nextInt();
            fib(N);
            System.out.println(dp[N][0] + " " + dp[N][1]);
        }
    }

    static Integer[] fib(int n) {
        if(dp[n][0] == null || dp[n][1] == null) {
            dp[n][0] = fib(n-1)[0] + fib(n-2)[0];
            dp[n][1] = fib(n-1)[1] + fib(n-2)[1];
        }
        return dp[n];
    }

}

참고
피보나치 수열의 int범위는 46번째까지이다.