[BJ] 백준 1003 피보나치 함수 (JAVA)

문제

https://www.acmicpc.net/problem/1003

 

풀이 방법

dp를 활용한 피보나치 관련된 문제다.
재귀호출을 사용해서 피보나치 수열을 구현할 때 0과 1을 호출하는 횟수를 출력해야한다. 
그래서 dp배열은 [수][0과1호출수]을 담을  2차원 배열로 선언해줬다. 

0일 때는 0호출 한번, 1일때는 1호출 한번이기 때문에 각각 1로 초기화해주고,
입력값의 최대값이 40이였기 때문에 나는 미리 40까지 다 구해주고, n에 따라서 출력해서 사용했다.
2부터 40까지 반복문을 돌리면서 i-1, i-2의 0과 1 호출 횟수를 더한 값을 각각 dp[n]에 저장해줬다.

그 이유는 재귀호출로 피보나치 수열을 구현했을때 처음부터 생각해보자. 그러면
f(2) = f(1) +f(0) 부터 시작할 것이다. 이 경우에는 f(1)은 1을 호출하고 1반환, f(0)은 0호출 후 0을 반환한다.
그러면 f(2)는 1호출 1회, 0호출 1회의 경우를 갖게 된다. 
이어서
f(3) = f(2) +f(1) 인 경우를 보면
f(2)은 위에서 1호출 1회, 0호출 1회를 구했고, 
f(1)은 1호출 1회, 0호출 0회이기 때문에 
f(3)은 1호출 2회 , 0호출 1회를 갖게 된다.

이런식으로 값을 40까지 넣어주게 되는 것이다.

 

제출 코드

import java.io.*;
import java.util.*;

public class BJ_1003_피보나치함수 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		int[][] dp = new int[41][2];
		dp[0][0] = 1;
		dp[1][1] = 1;
		for (int i = 2; i <= 40; i++) {
			dp[i][0] =dp[i-1][0]+ dp[i-2][0];
			dp[i][1] =dp[i-1][1]+ dp[i-2][1];
		}
		
		for (int test_case = 1; test_case <= T; test_case++) {
			int n =  Integer.parseInt(br.readLine());
			System.out.println(dp[n][0] +" "+dp[n][1]);
		}

	}
}