[JAVA/백준1003] 피보나치 함수 DP

1. 문제

 

2. 풀이

위 문제는 DP를 사용하지 않고 풀면 시간초과가 발생한다.
그래서 처음에는 메모이제이션으로 구현하려고 했지만, 예를 들어 이미 계산되어 메모제이션 배열에 저장되어 있는 경우에 0과 1을 어떻게 출력해야할지 고민하는데 시간이 많이 걸려서 결국 구글링을 해서 점화식을 세워 해결하였다.
점화식은 n=1일때부터 0과 1이 몇번 출력되는지를 세워보면 규칙을 찾아낼 수가 있다.

n	0호출	1호출
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3

n이 행(i)이고 0호출했을때와 1호출했을때를 열(j)이라고 하여 점화식을 세우면 다음과 같다.
f[i][j] = f[i-2][j] + f[i-1][j]
i=0, i=1인 경우에는 미리 초기화해둔다.

 

3. 소스코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt(); // 테스트 케이스 수
		int[][] f = new int[41][2]; // n, 0과 1
		f[0][0] = 1;
		f[1][1] = 1;
		// 0으로 초기화되므로 f[0][1]과 f[1][0]은 생략
		for (int i = 2; i <= 40; i++) {
			for (int j = 0; j < 2; j++) {
				f[i][j] = f[i - 2][j] + f[i - 1][j];
			}
		}

		for (int i = 0; i < t; i++) {
			int n = sc.nextInt();
			System.out.println(f[n][0] + " " + f[n][1]);
		}
		sc.close();
	}
}