백준 10826 피보나치 수 4 JAVA 풀이 (DP, BigInteger, 시간복잡도)

🔗 문제 링크

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

---

📌 문제 개요

피보나치 수열의 n번째 값을 구하는 문제
하지만 n의 범위가 매우 크기 때문에 일반적인 자료형으로는 해결할 수 없다.

---

📌 접근 방법

이 문제는 전형적인 DP(동적 계획법) 문제

• 이전 두 값을 이용하여 다음 값을 계산
• 재귀 대신 반복문 사용 (성능 고려)
• 핵심은 자료형 선택

---

📌 핵심 아이디어

• 피보나치 수는 n이 커질수록 값이 매우 빠르게 증가
• long 범위를 초과하기 때문에 사용 불가
• 따라서 BigInteger 사용 필수

BigInteger temp \= a.add(b);

 

BigInteger는 연산을 메서드로 수행해야 한다

---

📌 전체 코드

/*
문제-10826 (실버5): 피보나치 수 4
- n번째 피보나치 수를 출력하는 문제
- n의 범위가 매우 커서 일반 자료형으로는 처리 불가능

접근 방법
- 반복문을 이용한 Bottom-Up 방식 사용
- 이전 값 2개를 이용하여 현재 값 계산
- int/long 대신 BigInteger 사용

핵심 아이디어
- 피보나치 수는 n이 커질수록 값이 기하급수적으로 증가
- long 범위를 초과하기 때문에 BigInteger 사용 필수
- 덧셈은 add() 메서드 사용

처리 흐름
- 입력
- BigInteger a=0, b=1 초기화
- n==0이면 0 출력
- 반복문으로 피보나치 계산
- 결과 출력
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

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 a = BigInteger.ZERO;
        BigInteger b = BigInteger.ONE;

        if(n == 0){
            System.out.println(0);
            return;
        }

        for(int i = 2; i <= n; i++){
            BigInteger temp = a.add(b);
            a = b;
            b = temp;
        }

        System.out.println(b);
    }
}

---

🧾 정리

• 피보나치 자체는 쉬운 문제
• 하지만 자료형이 핵심 포인트
• 큰 수 문제 → BigInteger 바로 떠올리기