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

문제

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

1003번: 피보나치 함수

 

풀이

DP문제다.

DP를 이차원 배열로 선언했고 이차원 배열을 이용하여 0과 1의 개수를 저장했다.

i 번째의 0, 1의 개수를 구하고자 한다면, i-1 번째와 i-2번째의 0, 1의 개수를 더하면된다.

 

코드

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

public class Main {
	
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
       	int t = Integer.parseInt(br.readLine());
       	
       	int dp [][] = new int[41][2];

       	dp[0][0] = 1;
       	dp[1][0] = 0;
       	
       	dp[1][0] = 0;
       	dp[1][1] = 1;
       	       	
       	for(int task = 0; task < t; task++) {
       		int n = Integer.parseInt(br.readLine());
       		
       		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]);
       	}
       	
   }
   
}