2747 피보나치

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

 

[처음 생각한 접근 방법]

오늘 문제는 Dynamic Programming의 예제를 풀어보았습니다.

피보나치의 경우 f(n) = f(n-1) + f(n-2)라는 점화식이 나오는데 이를 구현하는 문제입니다.

Dynamic Programming을 이용하면 매번 f(n) 값을 구할 필요가 없습니다.

f(n)의 값을 한 번 구하면 그 값을 배열에 저장해놓았다가, 다시 이 값을 찾을 때 배열에 저장 되어 있는 값을 리턴하면 됩니다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {
    static int[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        // n번째 피보나치 수를 구하여라
        int n = Integer.parseInt(bfr.readLine());
        dp = new int[n+1];
        System.out.println(recursion(n));
    }

    private static int recursion(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (dp[n] != 0) return dp[n];	// 배열의 값이 0이 아니면 이전에 구한 값임.

        dp[n] = recursion(n-2) + recursion(n-1);
        return dp[n];
    }
}