[JAVA]백준_1003_피보나치함수

문제 : www.acmicpc.net/problem/1003  

1003번: 피보나치 함수

문제 유형 : dp

 

풀이방식 : 재귀로 풀때 시간초과 -> dp 메모이제이션 통과

               피보나치 0 일땐 1 0 출력 (0 한개 1 X)

               피보나치 1 일땐 0 1 출력 (0 X     1 한개)

               arr[x][0] = 숫자x일때 0의 개수

               arr[x][1] = 숫자x일때 1의 개수

               bottom-up 방식 : arr[i][0] = arr[i-1][0]+arr[i-2][0];
                                      arr[i][1] = arr[i-1][1]+arr[i-2][1];

 

 

소스코드

package BOJ;

import java.util.Scanner;

public class BOJ_1003_피보나치함수_Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int t = 0; t < T; t++) {
			 int n = sc.nextInt();
	            int[][] arr = new int[n+1][2];
	            
	            if(n==0) { // 0일때
	                System.out.println("1 0");
	                continue;
	            }
	            
	            if(n==1){ // 1일때
	                System.out.println("0 1");
	                continue;
	            }
	            
	            arr[0][0] = 1;
	            arr[1][1] = 1;
	            
	            for(int i=2; i<=n; i++){
	                arr[i][0] = arr[i-1][0]+arr[i-2][0];
	                arr[i][1] = arr[i-1][1]+arr[i-2][1];
	            }
	            System.out.println(arr[n][0]+" "+arr[n][1]);
	 
		}
	}

}