[백준 1003]피보나치 함수 - 자바

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

1003번: 피보나치 함수

 

1. 풀이

---

피보나치 수열을 재귀를 사용하여 풀때, 0과 1의 호출 횟수를 구하는 문제입니다.

 

피보나치의 재귀 동작 순서가 쓰여져있어서, 처음엔 피보나치 수열을 재귀적으로 풀어서 정답을 구하려다보니

 

시간 초과가 발생해서 DP를 사용하여 풀게 되었습니다.

 

우선, 피보나치의 0과 1의 호출 횟수는 아래와 같은 규칙을 가집니다.

 

n	memo[i][0] 0 호출 횟수	memo[i][1] 1 호출 횟수
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3

 

memo[i][j] = memo[i-1][j] + memo[i-2][j]

 

2. 코드

---

2.1 Bottom-Up

import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int num = sc.nextInt();
		
		int[][] memo = new int[41][2];
		
		memo[0][0] = 1;
		memo[0][1] = 0;
		memo[1][0] = 0;
		memo[1][1] = 1;
		
		int n;
		int[] idx = new int[num]; // 입력한 n을 인덱스 형태로 저장. (출력용)
		for(int i = 0; i < num; i++) {
			n = sc.nextInt();
			idx[i] = n;
			if(n == 0 || n == 1) // n이 0이나 1은 미리 대입했으므로 continue
				continue;
			for(int j = 2; j <= n; j++) {
				memo[j][0] = memo[j-1][0] + memo[j-2][0];
				memo[j][1] = memo[j-1][1] + memo[j-2][1];
			}
		}
		
		for(int i = 0; i < num; i++)
			System.out.println(memo[idx[i]][0]+" "+memo[idx[i]][1]);
		
		sc.close();
		return;
	}
}