DP - 1003. 피보나치 함수

문제

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		int[] results0 = new int[41];
		int[] results1 = new int[41];
		
		results0[0] = 1;
		results1[0] = 0;
		
		results0[1] = 0;
		results1[1] = 1;
		
		for (int i = 2; i < 41; i++) {
			results0[i] = results0[i-1] + results0[i-2];
			results1[i] = results1[i-1] + results1[i-2];
		}
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int testCase = Integer.parseInt(st.nextToken());

		for (int i = 0; i < testCase; i++) {
			st = new StringTokenizer(br.readLine());
			int inputNum = Integer.parseInt(st.nextToken());
			System.out.println(results0[inputNum] + " " + results1[inputNum]);
		}
	}
}

 

설명

fibonacci(0)은 0을 출력하고, 0을 리턴합니다.

fibonacci(1)은 1을 출력하고 1을 리턴합니다.

fibonacci(2)은 fibonacci(1) + fibonacci(0)입니다.

fibonacci(3)은 fibonacci(2) + fibonacci(1)입니다.

...

 

일정 패턴이 보이시죠?

피보나치 k의 0 호출 횟수는 k-1의 0 호출 횟수 + k-2의 0 호출 횟수입니다.

피보나치 k의 1 호출 횟수는 k-1의 1 호출 횟수 + k-2의 1 호출 횟수입니다.

값을 계산하고 저장해나아가면 되겠습니다.