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

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

10870번: 피보나치 수 5

 

 

---

• 문제

 

 

 

---

• 문제 풀이

백준 10870번 피보나치 수 5는 브론즈 5 난이도의 수학 및 구현 문제이다. 이 문제는 재귀 함수로도 풀 수 있지만 이번 포스트에서는 조금 더 효율적인 다이나믹 프로그래밍, 즉 DP 방식을 소개할까 한다. DP를 잘 모르면 밑에 있는 포스트를 참고하면 되겠다.

 

https://propercoding.tistory.com/4

[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming)

 

우선 이 문제는 20 이하인 정수 N이 주어지고 이 N이 주어졌을 때 N번째 피보나치 값을 출력하면 된다. n번째 피보나치 공식은 다음과 같다. 

 

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

 

간단히 설명해서 n번째 피보나치 수는 n - 1번째와 n - 2번째 피보나치 수를 더한 값이다. 그리고 첫 번째 피보나치 수는 1로 시작한다.

 

이 문제는 간단히 DP로 풀 수 있다. 우선 DP 배열을 초기화하고 첫 번째 값 DP [1] = 1로 초기화해준다. 그리고 for-loop을 이용해 i = 2부터 i = N까지 dp [i] = dp [i - 1] + dp [i - 2]를 해주면 된다. 

 

자세한 코드는 밑에 있다.

 

---

• 코드

 

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[21];  //DP 배열 초기화
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];  //피보나치 공식 이용
        }
        System.out.print(dp[n]);
    }
}