백준 1003 피보나치 함수 JAVA (DP)

1. 문제

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

1003번: 피보나치 함수

 

2. 설명

피보나치인데 조금 다른? 문제!

0의 수랑 1의 수를 계산해서 출력하는 문제인데,

출력하는 부분이 다를 뿐 기본적으로 피보나치랑 같다.

피보나치 결과를 저장하지 않고 각각 호출하는 0과 1의 수를 저장해두고 출력했다.

n의 최댓값이 40이라서 함수 크기는 41, 2는 0과 1을 저장해야 되므로 2로 잡았다.

 

3. 코드

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int T = scan.nextInt();
		int[] n = new int[T];
		int[][] fibonacci = new int[41][2];
		
		for(int i=0; i<T; i++) {
			n[i] = scan.nextInt();
		}
		
		fibonacci[0][0] = 1;
		fibonacci[0][1] = 0;
		fibonacci[1][0] = 0;
		fibonacci[1][1] = 1;
		for(int i=0; i<T; i++) {
			for(int j=2; j<=n[i]; j++) {
				fibonacci[j][0] = fibonacci[j-1][0] + fibonacci[j-2][0]; // 0의 수
				fibonacci[j][1] = fibonacci[j-1][1] + fibonacci[j-2][1]; // 1의 수
			}
			System.out.println(fibonacci[n[i]][0] + " " + fibonacci[n[i]][1]);
		}
	}
}