백준 자바 2748 피보나치 수2

문제

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

2748번: 피보나치 수 2

 

 

느낀점

동적프로그래밍에 대해 알게 되었다. 최대한 쉽게 말하자면 재귀적을 값을 구할 때 이전에 구했던 값이라면 다시 연산할 필요 없이 배열에 저장한 값을 꺼내는 방식이다.

 

 

해결방법

일반적으로 피보나치의 수는 재귀함수를 통하여 구할 수 있다. 여기서 동적계획법을 사용하면 더 빠르게 값을 구할 수 있다. 동적계획법이란 재귀적으로 함수를 작은 단위로 들어갈 때 값을 저장하여 이전에 저장한 값이 나오면 다시 연산하지 않고 배열에서 꺼내는 방법이다. 

 

 

소스코드

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

public class 문제_2748 {
    
    static long[] dp; // 동적 프로그래밍에서 값을 저장하기위해(메모이제이션) 배열 선언

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        dp = new long[n+1];  // 크기는 구하는 순서까지만 할당.

        for(int i=2; i<n+1; i++) {
            dp[i] = -1; // 값 -1은 사용하지 않았다는 의미
        }

        dp[0] = 0;  // 피보나치 초기값 설정
        dp[1] = 1;

        System.out.println(fibo(n));
    }

    public static long fibo(int N ) {

        if(dp[N] != -1)   // 값을 저장한 적이 있다면
            return dp[N];

        return dp[N] = fibo(N-1)  + fibo(N-2);  // 없다면
    }
}