Boj 1003 피보나치 함수

문제 링크 : 백준 https://www.acmicpc.net/problem/1003

실패 코드

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

public class Main {

	static int zero_cnt = 0;
	static int one_cnt = 0;
	static int N = 0;
	static StringBuilder sb = new StringBuilder();

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());

		for(int i = 0 ; i < N ; i++) {
		fibo(Integer.parseInt(br.readLine()));
		sb.append(zero_cnt).append(" ").append(one_cnt).append("\n");
		zero_cnt=0; one_cnt=0;
		}
		System.out.println(sb);
}
	public static void fibo(int n) {
		if(n==0) {
			zero_cnt++;
		} else if(n== 1) {
			one_cnt++;
		} else if(n < 0) return;
		else {
			fibo(n-1);
			fibo(n-2);
		}
	}
}

당연히 시간초과로 실패ㅎㅎ.. 메모이제이션 사용해서 풀기 ↓

성공 코드

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


public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static int[][] memo = new int[41][2];// N이 40보다 작거나 같으므로

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


		// memo -1로 초기화
		for (int i = 0; i < memo.length; i++)
			Arrays.fill(memo[i], -1);

		memo[0][0] = 1; // N=0 일 때의 0 호출 횟수
		memo[0][1] = 0; // N=0 일 때의 1 호출 횟수
		memo[1][0] = 0; // N=1 일 때의 0 호출 횟수
		memo[1][1] = 1; // N=1 일 때의 1 호출 횟수

		int T = Integer.parseInt(br.readLine());

		for (int i = 0; i < T; i++) {
			int N = Integer.parseInt(br.readLine());
			fibonacci(N);
			System.out.println(memo[N][0] + " " + memo[N][1]);
		}

	}

	static int[] fibonacci(int N) {
		// 탐색하지 않은 값일 경우
		if (memo[N][0] == -1 || memo[N][1] == -1) {
			// 각 N에 대한 0 호출 횟수와 1 호출 횟수를 재귀호출.
			memo[N][0] = fibonacci(N - 1)[0] + fibonacci(N - 2)[0];
			memo[N][1] = fibonacci(N - 1)[1] + fibonacci(N - 2)[1];
		}
		// [N][0]과 [N][1] 을 담고있는 [N]을 반환.
		return memo[N];

	}

}