백준1003 피보나치 함수 (동적계획법)

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

1003번: 피보나치 함수

배운점

동적계획법을 이용해서 푸는 문제였다. 처음에는 그냥 재귀함수를 이용해 호출된 횟수를 전역변수로 두고 카운트를 해서 제출했는데 시간초과가 발생하였다.

동적계획법의 개념에 대해 아직 익숙하지 않지만 현재 도출해내야 할 결과에 이전의 계산값이 영향을 미치면 동적계획법을 활용 할 수 있다는 것을 배웠다. 이 문제의 경우 0,1이 호출되는 횟수를 각각 저장해야하므로 2차원 배열을 이용해서 문제를 해결했다. 

 

풀이

package 동적계획법;
 
import java.io.*;
import java.util.Arrays;
 
public class 피보나치함수 {
    static long[] res = new long[40];
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
 
        for (int i = 0; i < n; i++) {
            int temp = Integer.parseInt(br.readLine());
            int [][] ar = new int[temp+1][2];
            if(temp==0){
                System.out.println(1+" "+0);
                continue;
            }
            else if(temp==1){
                System.out.println(0+" "+1);
                continue;
            }
            ar[0][0] = 1;
            ar[1][1] = 1;
            for(int j=2;j<=temp;j++){
                ar[j][0] = ar[j-1][0]+ar[j-2][0];
                ar[j][1] = ar[j-1][1]+ar[j-2][1];
            }
            System.out.println(ar[temp][0]+" "+ar[temp][1]);
        }
 
    }
 
}