자바로 백준 1003 풀기

풀이)
피보나치 수에서 0과 1이 호출되는 횟수를 구하기 위해 이 과정을 DP로 풀어내면 된다. 즉, 한 번 탐색할 때마다 해당 N의 0과 1의 값을 저장해두고, 이후 다음 탐색에서 이미 탐색했던 노드일 경우 해당 배열값을 쓰면 된다.
1. N에 대한 0호출 횟수 = N-1의 1 호출 횟수
2. N에 대한 1 호출 횟수 = N-1의 0 호출 횟수 + N-1의 1 호출 횟수

내 코드)

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];
 
	}
 
}