[백준] 2748번 : 피보나치 수 2 – JAVA [자바]

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

2748번: 피보나치 수 2

 

---

• 문제

 

 

---

• 문제 풀이

백준 2748번 피보나치 수 2는 브론즈 1 난이도의 수학 및 DP 문제이다. 이 문제에서는 정수 N이 주어진다. 이때 N번째 피보나치 수를 출력하면 된다.

 

이 문제는 재귀 함수를 이용해서도 풀 수 있겠지만 더 효율적인 DP(다이나믹 프로그래밍)을 이용해서 풀 것이다. DP가 재귀 함수보다 더 효율적인 이유는 재귀 함수로 풀면 풀었던 것을 반복해서 또 풀고 또 풀고 해야 한다. 하지만 DP에서는 한번 계산한 것은 저장해 두어서 (메모이제이션) 재귀 함수보다 더 효율적이라고 할 수 있다.

 

우선 DP 배열 dp를 선언한다. 이 배열은 long형을 저장할 것이다. 왜냐하면 90번째 피보나치 수는 int형의 범위를 초과하기 때문이다. 만약에 long형의 범위도 초과하면 그때는 BigInteger를 사용해야 한다. 

 

그리고 N번째 피보나치 수는 N - 1번째 + N - 2번째 피보나치 수이다. 따라서 dp [1] = 1로 설정해두고 i = 2부터 for 문을 이용해서 dp [i] = dp [i - 1] + dp [i - 2]를 해주면 된다. 그리고 for문이 끝나면 dp [n]을 출력해주면 된다.

 

자세한 코드는 밑에 있다.

 

---

• 코드

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long[] dp = new long[91];  //DP 배열
        dp[1] = 1;
        int n = Integer.parseInt(br.readLine());
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2]; 
        }
        System.out.print(dp[n]);
    }
}