[알고리즘] 백준 1003 자바 Java

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

public class BaekJoon_16_1003 {

	private static int[][] dp;

	private static void fibonacci(int n) {
		for (int i = 2; i <= n; i++) {
			dp[i][0] = dp[i - 1][0] + dp[i - 2][0];
			dp[i][1] = dp[i - 1][1] + dp[i - 2][1];
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

		dp = new int[41][2];
		dp[0][0] = 1;
		dp[0][1] = 0;
		dp[1][0] = 0;
		dp[1][1] = 1;

		int n = Integer.parseInt(reader.readLine());

		for (int i = 0; i < n; i++) {
			int f = Integer.parseInt(reader.readLine());
			fibonacci(f);
			writer.write(dp[f][0] + " " + dp[f][1]);
			writer.newLine();
		}

		reader.close();
		writer.flush();
		writer.close();
	}

}

 

피보나치 문제는 dp문제의 기본이다. 하향식이던 메모이제이션을 하던 두가지 버전으로 풀 수 있다. 근데 이 문제는 약간 다르다. 기존의 피보나치 문제는 원하는 답을 얼마나 빠르게 구하느냐 였다면 이 문제는 실제 n이 0과 1의 호출 개수를 구하는 문제이다. 그래서 음 쉽군 하고 접근하면 앗! 하는 문제.

 

재귀문제로 접근할 때는 메모이제이션으로 0일때를 제외하고 풀면되지만 실제 0과 1의 호출을 묻는 문제이기 때문에 생각을 달리해야 한다. 이럴때는 직접 호출해보고 호출의 규칙을 찾는 것도 방법이고, 이 문제는 그렇게 접근해야 한다.

 

생각의 전환!