[백준] 1003 피보나치 함수

일반적으로 다이나믹 프로그래밍을 이용하여 피보나치 함수를 구현하는 방법을 그대로 이용하면된다. 

다른점은 0을 출력하는 것과 1을 출력하는 것을 따로 저장하여 

다음 값의 호출에 0과 1을 출력하는 경우를 모두 더하여 출력하면 된다. 

dp[N][0] : N번째 수의 0 출력 횟수

dp[N][1] : N번째 수의 1 출력 횟수

i번째 수의 0과 1출력 횟수는 다음과 같다. 

dp[i][0] = dp[i-2][0] + dp[i-1][0];

dp[i][1] = dp[i-2][1] + dp[i-1][1];

	import java.util.Scanner;
	/**
	* 백준, 1003, 피보나치 함수
	*
	* @author whitebeard
	*
	*/
	public class Problem1003 {
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int T = sc.nextInt();
	int[][] dp = new int[41][2];
	dp[0][0] = 1;
	dp[1][1] = 1;
	for (int i = 0; i < T; i++) {
	fibonacciPrint(dp, sc.nextInt());
	}
	sc.close();
	}
	public static void fibonacciPrint(int[][] dp, int n) {
	if (n >= 2 && dp[n][0] == 0 && dp[n][1] == 0) {
	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];
	}
	}
	System.out.printf("%d %d\n", dp[n][0], dp[n][1]);
	}
	}

view raw Problem1003 hosted with ❤ by GitHub