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

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

2747번: 피보나치 수

 

---

• 문제

 

 

---

• 문제 풀이

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

 

피보나치의 공식은 다음과 같다.

 

 fib(n) = fib(n - 1) + fib(n - 2)

 

이 문제는 DP(다이나믹 프로그래밍)를 이용하면 효율적으로 풀 수 있다. 우선 N을 입력받는다. 그리고 N의 범위가 45까지이다 보니 크기가 46인 int형 배열 dp를 만들어주고 dp [1]은 1로 초기화해준다.

 

이제 for 문으로 int i = 2부터 N까지 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));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[46];  //DP 배열
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        System.out.print(dp[n]);
    }
}