[BOJ 1003번] 피보나치 함수(JAVA)

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

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

class Main{
	
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb=new StringBuilder();
	static int N;
	static int[][] arr=new int[41][2];
	
	public static void main(String args[]) throws Exception {
		N=Integer.parseInt(br.readLine());
		arr[0][0]=1;
		arr[0][1]=0;
		arr[1][0]=0;
		arr[1][1]=1;
		for(int i=2;i<41;i++) {
			arr[i][0]=arr[i-1][0]+arr[i-2][0];
			arr[i][1]=arr[i-1][1]+arr[i-2][1];
		}
		for(int i=0;i<N;i++) {
			int temp=Integer.parseInt(br.readLine());
			sb.append(arr[temp][0]+" "+arr[temp][1]+"\n");
		}
		System.out.println(sb);
	}
	
}

처음에는 재귀를 이용한 방법으로 풀었다가 시간 초과에 막혔습니다.

시간 초과를 줄일 방법을 찾던 중 배열을 이용해 이중배열 arr[i][0]에 i번째 피보나치 수에서 0번째 피보나치 수가 쓰인 횟수, arr[i][1]에 i번째 피보나치 수에서 1번째 피보나치 수가 쓰인 횟수를 저장해 i가 40이 될 때까지 저장했습니다.