자바로 백준 1003 풀기

• 실버 5단계

풀이)
만약 처음에 N=20 이 입력되어 20에 대해 0과 1 호출횟수를 구한다면 Fibonacci(19) 에 대해서도 자연스럽게 구해질 것이고, Fibonacci(18), Fibonacci(17), ⋯ 해서 N 이하의 모든 수들은 자연스럽게 0과 1을 찾기위해 하위단계로 재귀호출될 것이다.

즉, N=20 에 대해 구한다음에 만약 N=15 같이 이하의 수가 입력된다면 또 다시 재귀호출 할 필요 없이 이미 연산과정에서 한 번 탐색이 이루어졌으므로 바로 해당 값을 꺼내면 된다.

내 코드)

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();
        
		StringBuilder sb = new StringBuilder();
 
		while(T-- > 0){
			int N = in.nextInt();
			fibonacci(N);
			sb.append(dp[N][0] + " " + dp[N][1]).append('\n');
		}
		System.out.print(sb);
	}
	
	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];
 
	}
 
}