[JAVA] 백준 2748_피보나치 수 2

 

[문제링크]

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

 

 

📌 문제 탐색하기

피보나치 수 문제로서 피보나치 수열을 활용한 방식의 문제이다. 

피보나치 수열을 해결하는 가장 기본적인 방법은 재귀를 활용한 방식이므로 재귀적으로 접근할 계획이다.

  Fn = Fn-1 + Fn-2 (n ≥ 2) 의 규칙을 가지고 있는 수열으로 입력값 n에 따라서 n번째 피보나치 수를 출력하는 문제이다.

 

📌 가능한 시간복잡도 & 실수 정리

n의 값이 더 크게 입력 받아지는 경우 시간 초과가 발생 주의가 필요하다고 생각함... 이 부분은 조금 더 고민해 볼 필요가 있음. 

=> 실제로 시간 초과로 실패함... 이런 경우 해결 방법을 찾아보니 DP를 활용해서 문제를 풀어야한다고 함...

 

2회차 다른 풀이 도전 ) 배열을 이용해서 DP 알고리즘 방식으로 풀었음

    각각 피보나치 수를 한번씩만 계산해서 저장하니까 중복 계산이 방지되어서 시간 초과가 일어나지 않은것으로 보임.

    

    DP는 O(N)의 시간 복잡도를 가지고 있기 때문에 N의 값이 큰값이 입력되어도 시간 초과없이 빠르게 동작이 가능하다. 

 

따라서, 가능한 시간 복잡도는 O(n)이라고 생각합니다. 

 

📌 코드 설계하기

1회차) fibonacci 함수 사용해야한다.

• 입력값 n이 0일 경우 0을 반환하고 1일 경우 1을 반환
• n≥2인 경우는 F(n)=F(n−1)+F(n−2) 의 식 재귀를 활용해서 호출하는 알고리즘을 사용하면 된다고 함.

2회차) 동적 프로그래밍(DP) 방식을 사용해야 시간초과 문제 해결이 가능하다. 

• fib[i] = fib[i - 1] + fib[i - 2]; 으로 fib[i] 는 i번째 피보나치 수를 저장하는 배열이다. 
•  

📌 정답 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt(); 
        long[] fib = new long[n + 1];

        fib[0] = 0; 
        if (n > 0) {
            fib[1] = 1;
        }

        //DP를 적용한 부분
        for (int i = 2; i <= n; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }

        System.out.println(fib[n]);
        
        sc.close();
    }
}