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

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

1003번: 피보나치 함수

---

 

문제

 

 

풀이

문제는 fibonacci(N)을 호출했을 때 0과 1이 출력되는 횟수를 각각 구해야 하기 때문에 0과 1의 경우를 나누어 저장해야합니다.

따라서 dp 테이블을 2차원 배열로 하여 dp[i][0] 은 fibonacci(i)를 호출했을 때 0이 출력되는 횟수, dp[i][1]는 fibonacci(1)을 호출했을 때 1이 출력되는 횟수로 합니다.

 

따라서 dp[0][0] = 1, dp[1][1] = 1이 됩니다.

 

피보나치 수열을 dp로 푸는 방법을 간단하게 설명해보겠습니다.

피보나치 수열을 문제의 C++ 코드 처럼 풀게 되면 fibonacci(i)는 fibonacci(i-1) + fibonacci(i-2) 로 풉니다. 그리고 i가 0이나 1이 되면 각각 0과 1을 리턴하여 0과 1을 호출된 만큼 더하여 구합니다. 이렇게 풀게 되면 같은 연산을 중복해서 계산해야 하기 때문에 굉장히 오랜 시간이 걸립니다.

 

따라서 이미 계산된 값은 dp 테이블에 저장하여 중복된 계산을 하지 않도록 하는 것이 효율적입니다.

 

2부터 구하고자 하는 N까지의 dp 테이블을 순차적으로 계산한 뒤, dp[N]을 출력하면 N번째 피보나치 수를 구할 수 있게 됩니다. 이 때 점화식은 dp[i] = dp[i-1] + dp[i-2] 가 됩니다.

 

이 점화식을 2차원 배열로 만들어 0과 1의 개수를 저장해주면 됩니다.

하나씩 살펴보면 다음과 같습니다.

행/열	0	1	2	3	4
0	1	0	dp[2-1][0] + dp[2-2][0] = 1	dp[3-1][0] + dp[3-2][0] = 1	dp[4-1][0] + dp[4-2][0] = 2
1	0	1	dp[2-1][1] + dp[2-2][1] = 1	dp[3-1][1] + dp[3-2][1] = 2	dp[4-1][1] + dp[4-2][1] = 3

 

 

소스코드

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

public class BJ1003 {
	
	// 0 <= N <= 40, 0과 1의 경우(2가지)
	static int[][] dp = new int[41][2];

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		for(int t=0; t<T; t++) {
			int N = Integer.parseInt(br.readLine());
			
			// 0에서 0은 1번 출력, 1에서 1은 한번 출력
			dp[0][0] = 1;
			dp[1][1] = 1;
			
			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.println(dp[N][0] + " " + dp[N][1]);
		}
	}

}