[백준] 10870번 : 피보나치 수 5 (JAVA)

🔗 문제 링크

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

---

📌 문제 개요

피보나치 수열의 n번째 수를 구하는 문제이다.

피보나치 수열은 다음과 같이 정의

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2)

입력으로 정수 n이 주어질 때, n번째 피보나치 수를 출력

---

📌 접근 방법

피보나치 문제는 보통 재귀로 먼저 떠올리기 쉽다.

하지만 재귀 방식은 동일한 계산이 반복되어 **시간 복잡도가 O(2ⁿ)**으로 증가한다.

이번 문제는 n ≤ 20으로 범위가 작지만,
실전 습관을 위해 반복문(Iterative) 방식으로 풀이

• 이전 두 값을 저장하면서
• 다음 값을 계속 누적 계산하는 방식

시간 복잡도는 O(n) 이다.

---

📌 핵심 아이디어

피보나치는 직전 두 값만 필요, 그리고 값을 한 칸씩 밀어주면 된다.

 

current = prev1 + prev2

 

즉, 배열 없이 변수 2~3개만으로 해결 가능

prev2 = prev1
prev1 = current

 

---

📌 전체 코드

package no_10870;

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

public class No10870 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

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

        int prev2 = 0;
        int prev1 = 1;
        int current = 0;

        for (int i = 2; i <= n; i++) {
            current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }

        System.out.println(current);
    }
}

---

📌 정리

- 피보나치는 대표적인 DP(동적 계획법) 기초 문제

- 재귀보다는 반복문이 성능상 안정적

- 이전 두 값만 유지하면 되므로 메모리 사용도 최소