피보나치 함수

난이도: 실버3
알고리즘 분류: DP
문제링크

실패 코드

package solution;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BOJ1003_피보나치함수 {
    static long[] memo;
    static int zeroCnt, oneCnt;
    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());
        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            memo = new long[N+1];
            zeroCnt = 0;
            oneCnt=0;
            fibonacci(N);
            sb.append(zeroCnt).append(" ").append(oneCnt).append("\n");
        }
        System.out.println(sb);
    }

    private static long fibonacci(int n) {
        if(n==0) {
            zeroCnt++;
            return 0;
        }
        if(n==1) {
            oneCnt++;
            return 1;
        }
        if(memo[n] == 0) return fibonacci(n-1) + fibonacci(n-2);
        return memo[n];
    }
}

처음 문제를 보고는 메모이제이션을 이용해 0,1을 각각 카운트해야겠다고 생각했고, 답은 맞게 나왔지만 시간초과가 났다.

통과 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int[][] fibo;
    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());
        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            fibo = new int[N+1][2];
            fibo[0][0] = 1;
            if(N>0) fibo[1][1] = 1;
            for (int j = 2; j <= N; j++) {
                fibo[j][0] = fibo[j-1][0] + fibo[j-2][0];
                fibo[j][1] = fibo[j-1][1] + fibo[j-2][1];
            }
            sb.append(fibo[N][0]).append(" ").append(fibo[N][1]).append("\n");
        }
        System.out.println(sb);
    }
}

0이 호출되는 횟수와 1이 호출되는 횟수를 가지고 있는 2차원 배열을 생성 후 표를 그려보니,
현재 피보나치 배열은 이전과 그 이전값 두개를 합친 것과 같다는 점화식을 도출할 수 있었다.

결과