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

백준 No1003_피보나치함수

문제 이해

이 문제는 피보나치 수를 구할 때 0과 1이 몇번씩 호출되는지 구하는 문제이다. 예를들어 fibonacci(3)이면

fibonacci(3) = fibonacci(1) + fibonacci(2)
fibonacci(1) = 1
fibonacci(2) = fibonacci(0) + fibonacci(1)
fibonacci(0) = 1
fibonacci(1) = 1
이므로 0은 1번 1은 2번 나오는 과정을 거치게 된다.

접근 방법

이 문제는 그냥 재귀함수 호출을 통해 답을 구하면 시간 초과가 난다. 피보나치 함수의 재귀함수를 이용하면 구하려는 피보나치수가 조금만 커져도 호출해야하는 함수의 수가 엄청나게 많아진다.
따라서 이 문제는 동적계획법(=Dynamic Programming,DP)를 사용해야한다.

재귀함수를 호출하면서 이미 구했던 피보나치 수이면 memo배열에 0과 1에 대한 정보를 저장한다. 그리고 나중에 이 피보나치 수를 다시 구해야할 때 memo배열에서 정보를 가져온다.

import java.io.*;

public class No1003_피보나치함수 {

    static int memo[][] = new int[41][2];
    //n이 최소 0 최대 40이므로 크기는 41

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());

        for (int i=0;i<41;i++) {
            for (int j=0;j<2;j++) {
                memo[i][j]=-1;
            }
        }//메모가 안된 배열을 구분하기 위해 -1로 초기화

        for (int i = 0; i < tc; i++) {
            int n = Integer.parseInt(br.readLine());
            fib(n);
            System.out.println(memo[n][0]+" "+memo[n][1]);
        }
    }

    public static int[] fib(int n) {
        if (memo[n][0] == -1 || memo[n][1] == -1) { // 처음 구하는 값이면
            if (n == 0) {
                memo[n][0]=1;
                memo[n][1]=0;
            }
            else if (n == 1) {
                memo[n][1]=1;
                memo[n][0]=0;

            }
            else {
                memo[n][0] = fib(n - 2)[0] + fib(n - 1)[0];
                memo[n][1] = fib(n - 2)[1] + fib(n - 1)[1];
            }
        }
        return memo[n]; 
    }
}

처음에 memo배열 (0과 1에 대한 정보)를 리턴해야한다는 생각은 했는데 피보나치수도 리턴해야한다고 생각해서 삽질을 많이 했다. 피보나치 문제이지만 피보나치값을 리턴할 필요는 없다!!!