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

문제

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

풀이

피보나치 수열:

f(5)
= f(4) + f(3)
= [ f(3) + f(2) ] + [ f(2) + f(1) ]
= [ [ f(2) + f(1) ] + [ f(1) + f(0) ] ] + [ [ f(1) + f(0)] + f(1) ]

= [ [ f(1) + f(0) ] + f(1) + [ f(1) + f(0) ] ] + [ [ f(1) + f(0) ] + f(1) ]

 

일반적인 피보나치 수열 구하는 방법:

int fib(int n){
	if(n==0) return 0;
    if(n==1) return 1;
    return fib(n-1) + fib(n+1);
}

 

Dynamic Programming(동적 계획법) :

주어진 문제를 작은 문제로 쪼개서 풀어나갈 때, 반복 호출을 줄이는 방법.
이미 구해진 값을 재사용하는 것이 핵심이다. 이를 메모제이션(Memozation)이라고 한다.

구해진 값을 배열에 저장하여 피보나치 수행 시 배열에 값이 있다면 그 값을 불러오고, 없다면 재귀를 수행한다.

int[] arr = new arr[n+1]; //모든 값을 -1로 초기화

arr[0] = 0;
arr[1] = 1;

int fib(int n){
    if(arr[n] == -1)
    	arr[n] = fib(n-1) + fib(n+1);
    return arr[n];
}

 

이 문제에서는 f(n)을 실행했을 때 0과 1이 몇 개 나오는지 출력해야 하므로 이차원 배열을 사용했다.

arr[n][0] = f(n)일 때 0의 개수 저장

arr[n][1] = f(n)일 때 1의 개수 저장

 

주어진 시간이 0.25초이므로 25,000,000번 안으로 연산을 끝내야 한다.

N의 최댓값은 40이다.

 

재귀함수로 구현된 피보나치 수열의 시간복잡도는 O(2^N)이다. 이는 O(N^2)보다 훨씬 가파르게 상승한다.

만약 이전 계산 결과를 재사용하지 않고 재귀함수로만 값을 구한다면 최악의 경우 2^40= 1,099,511,627,776 번의 연산이 필요하다.

 

코드

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

public class Main {
    static int[][] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        for(int k=0; k<N; k++){
            int n = Integer.parseInt(br.readLine());

            arr = new int[n+2][2];
            for(int i=0; i<n+2; i++){
                for(int j=0; j<2; j++){
                    arr[i][j] = -1;
                }
            }

            arr[0][0] = 1;
            arr[0][1] = 0;
            arr[1][0] = 0;
            arr[1][1] = 1;

            bw.write(fib0(n) + " ");
            bw.write(fib1(n)+ " ");
            bw.write("\n");
        }
        bw.close();
    }
    static int fib0(int n){
        if(arr[n][0] == -1){
            arr[n][0] = fib0(n-1) + fib0(n-2);
        }
        return arr[n][0];
    }
    static int fib1(int n){
        if(arr[n][1] == -1){
            arr[n][1] = fib1(n-1) + fib1(n-2);
        }
        return arr[n][1];
    }
}