BOJ - 피보나치 함수

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

1003번: 피보나치 함수

 

• BOJ - 동적 계획법 1단계 문제집에 수록되어있다.
  • https://www.acmicpc.net/step/16
• 0, 1각각 배열에 저장하며 피보나치 탐색 시 갱신하였다.

동적 계획법 1 단계

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
    public static final Scanner scanner = new Scanner(System.in);
    public static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static int[] memo;

    public static int[] zero;
    public static int[] one;

    public static StringBuilder builder = new StringBuilder();

    public static void main(String[] args) throws Exception {
        int T = scanner.nextInt();

        while (T-- > 0) {
            int N = scanner.nextInt();
            zero = new int[N + 2];
            one = new int[N + 2];
            memo = new int[N + 1];
            Arrays.fill(memo, -1);
            fibonacci(N);
            builder.append(String.format("%d %d\n", zero[N], one[N]));
        }
        System.out.println(builder);
    }

    private static int fibonacci(int N) {
        if (N == 0) {
            zero[N] = 1;
            one[N] = 0;
            return 0;
        }
        if (N == 1) {
            zero[N] = 0;
            one[N] = 1;
            return 1;
        }

        if (memo[N] == -1) {
            memo[N] = fibonacci(N - 1) + fibonacci(N - 2);
            one[N] = one[N - 1] + one[N - 2];
            zero[N] = zero[N - 1] + zero[N - 2];
            return memo[N];
        } else {
            return memo[N];
        }
    }
}