백준 2747번 : 피보나치 수 [Java]

문제 링크

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

2747번: 피보나치 수

문제 설명

코드(1) - 시간초과

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static int fibo(int n) {
        if (n <= 1) {
            return n;
        } else {
            return fibo(n - 1) + fibo(n - 2);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

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

코드(2) - OK

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        
        int[] dp = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            dp[i] = -1;
        }

        //가장 작은 영역 초기화
        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        System.out.println(dp[n]);    
    }
}

풀이

1. 피보나치 수식으로 표현하면 f(n)=f(n-2)+f(n-1)인데 재귀함수로 풀면 중복계산되어 시간 오래 걸린다.

2. DP(다이나믹 프로그래밍)를 이용하면 시간 복잡도를 줄일 수 있다. 

3. int형 배열 dp를 만들어주고 dp [0], dp [1]은 1로 초기화해준다. -> 처음 값을 초기화

4. for 문으로 int i = 2부터 N까지 dp [i] = dp [i - 1] + dp [i - 2]를 해준다. 그리고 for 문이 끝나면 dp [N]을 출력해준다.