[1003번] 피보나치 함수 JAVA☕

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

1003번: 피보나치 함수

---

풀이법

일단 이번 문제는 피보나치 수를 구하는 것이 아니라 피보나치 수에서 0과 1이 호출되는 횟수를 구하는 것이다.
코드로는 N이 최대 40까지 주어지고, 각 N에 0과 1이 호출된 횟수를 담아야 하므로 2차원 배열이 필요하다.
(또한 null 체크를하기 위해서 int[][] 가 아닌 Integer[][]로 사용한다.)

DP라는 배열을 선언하고, 피보나치 함수는 각 N에 대한 0과 1의 값을 DP에 저장하면서 재귀호출을 진행한다.

N에 대한 0과 1은 다음과 같은 규칙을 따른다.
1. N에 대한 0호출 횟수 = N-1의 1 호출 횟수
2. N에 대한 1호출 횟수  = (N-1의 0 호출횟수) + (N-1의 1 호출 횟수)

위 설명을 코드로 보면 다음과 같다.

// 기본 값(N=0일 때)
int zero = 1;
int one = 0;
int zero_plus_one = 1;
 
for (int i = 0; i < N; i++) {
    zero = one;    // 0호출 횟수를 이전의 1호출 횟수로 변경
    one = zero_plus_one;    // 1호출 횟수를 이전의 0과 1호출 횟수의 합으로 변경
    zero_plus_one = zero + one;    // 0과 1 호출의 합 계산
}

---

재귀적으로 구현한 코드

package com.linerate;
import java.util.Scanner;
public class Main {
    static Integer[][] dp = new Integer[41][2];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        dp[0][0] = 1;    // N=0 일 때의 0 호출 횟수
        dp[0][1] = 0;    // N=0 일 때의 1 호출 횟수
        dp[1][0] = 0;    // N=1 일 때의 0 호출 횟수
        dp[1][1] = 1;    // N=1 일 때의 1 호출 횟수
        int T = in.nextInt();
        while(T-- > 0){
            int N = in.nextInt();
            fibonacci(N);
            System.out.println(dp[N][0] + " " + dp[N][1]);
        }
    }
    static Integer[] fibonacci(int N) {
        // N에 대한 0, 1의 호출 횟수가 없을 떄(탐색하지 않은 값일 때)
        if(dp[N][0] == null || dp[N][1] == null) {
            // 각 N에 대한 0 호출 횟수와 1 호출 횟수를 재귀호출한다.
            dp[N][0] = fibonacci(N - 1)[0] + fibonacci(N - 2)[0];
            dp[N][1] = fibonacci(N - 1)[1] + fibonacci(N - 2)[1];
        }
        // N에 대한 0과 1, 즉 [N][0]과 [N][1] 을 담고있는 [N]을 반환한다.
        return dp[N];
    }
}