[백준 1003 / Java / 실버3] 피보나치 함수

문제

 
기본적인 피보나치 함수 문제이다. 일반적으로 재귀 또는 DP 형태로 풀 수 있다.
이 문제에서는 시간제한이 0.25초로 짧기 때문에 DP로 풀어야 한다.
 

import java.io.*;

public class Main {
	
	static int zeroResult = 0;
	static int oneResult = 0;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		for (int i = 0; i < T; i++) {
			
			int value = Integer.parseInt(br.readLine());
			fibo(value);
			System.out.printf("%d %d", zeroResult, oneResult);
			
			initialization();
		}
	}
	
	private static int fibo(int n) {
		if (n == 0) {
			zeroResult += 1;
			return 0;
		}
		else if (n == 1) {
			oneResult += 1;
			return 1;
		}
		else {
			return fibo(n-1) + fibo(n-2);
		}
	}
	
	private static void initialization() {
		zeroResult = 0;
		oneResult = 0;
	}
}

 
첫 번째 시도 코드다. 최대 N이 40이라 0.25초여도 풀리지 않을까? 싶어서 그냥 재귀로 풀어봤는데, 시간초과가 떴다.
어쩔수 없이 DP로 풀기로 결정.
 

import java.io.*;

public class 피보나치_함수_1003 {
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		/**
		 * [ [현재숫자, 0호출횟수, 1호출횟수] ... ]
		 * [ [0, 1, 0], [1, 0, 1], [1, 1, 1] ... ]
		 */
		int[][] fiboTable = new int[41][3];
		fiboTable[0] = new int[] {0, 1, 0};
		fiboTable[1] = new int[] {1, 0, 1};
		
		for (int i = 2; i < fiboTable.length; i++) {
			fiboTable[i] = new int[] {
					fiboTable[i-1][0] + fiboTable[i-2][0],
					fiboTable[i-1][1] + fiboTable[i-2][1],
					fiboTable[i-1][2] + fiboTable[i-2][2]
			};
		}
		
		int T = Integer.parseInt(br.readLine());
		for (int i = 0; i < T; i++) {
			
			int value = Integer.parseInt(br.readLine());
			System.out.printf("%d %d\n", fiboTable[value][1], fiboTable[value][2]);
		}
	}
}

 
일반적인 피보나치 수열 구하는 문제는 이전값 + 전전값 = 현재값 인데,
이 문제에서는 단순 N번째 값을 출력하는 게 아니라 N이라는 값을 출력하기 위해 호출된 0, 1 재귀 횟수를 각각 출력해야 한다.
 
크게 어렵지 않다. 그냥 값 구할 때 0, 1 호출 횟수도 같이 더해주면 끝!
 
fiboTable의 요소는 이렇다. -> [ 현재 값, 0호출횟수, 1호출횟수 ]
그래서 이렇게 초기화를 한 후에 -> [[ 0, 1, 0 ], [1, 0, 1]]
전부 다 더하면 끝이다. 값이든 호출횟수든 이전값, 전전값을 더하면 똑같이 구할 수 있는 것이다.
 
근데 난 실제 N번째 값까지 함께 구했는데, 그냥 저거 빼고 호출횟수만 더해도 되긴 한다. 그래도 직관성, 가독성을 위해서.. 함께 계산했다.