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

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

10826번: 피보나치 수 4

 

---

• 문제

 

---

• 문제 풀이

백준 10826번 피보나치 수 4는 DP와 BigInteger를 이용해서 푸는 문제이다. DP나 BigInteger 이론을 공부하고 싶으면 밑에 있는 링크들을 참고하면 되겠다.

 

https://propercoding.tistory.com/entry/알고리즘-다이나믹-프로그래밍-Dynamic-Programming

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

https://propercoding.tistory.com/entry/알고리즘-큰-숫자-정수-BigInteger-사용법-JAVA-자바

[알고리즘] 큰 숫자 (정수) BigInteger 사용법 - JAVA [자바]

피보나치 수열은 fib(n) = fib(n-2) + fib(n-1)과 같다. 이것을 BigInteger를 사용해서 표현하면 다음과 같다.

dp [n] = dp[n-2].add(dp[n-1])

여기서 배열 dp는 BigInteger를 담고 있다.

 

 

---

• 코드

import java.math.BigInteger;
import java.util.*;
import java.io.*;
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());
        BigInteger[] dp = new BigInteger[10001];
        dp[0] = new BigInteger("0");
        dp[1] = new BigInteger("1");
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i-2].add(dp[i-1]);
        }
        System.out.print(dp[n]);
    }
}

 

---

• 후기

BigInteger를 모르는 상태였으면 문제를 이해해도 절대 풀 수 없는 문제이다. BigInteger를 이용해서 푸는 문제가 간간히 나오므로 BigInteger를 이해하는 게 되게 중요하다.