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

📌 문제 링크

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

---

📌 문제 개요

정수 n이 주어질 때 n번째 피보나치 수 F(n) 을 출력
피보나치 정의는 다음과 같다.

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

---

📌 접근 방법

피보나치 수는 이전 두 값만 알면 다음 값을 만들 수 있다.
따라서 배열을 만들지 않고 a(F(n-2)), b(F(n-1)) 두 변수만 이용해 반복문으로 계산

---

📌 핵심 아이디어

• a=0, b=1로 시작
• temp = a + b로 다음 피보나치 생성
• a=b, b=temp로 값 갱신
• 반복이 끝나면 b가 F(n)

예외 처리: n=0이면 바로 0 출력

---

📌 전체 코드

package no_2747;

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

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

        int a = 0; // F(0)
        int b = 1; // F(1)

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

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

        System.out.println(b);
    }
}

---

📌 정리

• 피보나치 수는 이전 두 항만으로 다음 항을 만들 수 있다.
• 반복문으로 계산하면 시간복잡도 O(n)
• 배열을 쓰지 않아 공간복잡도 O(1)로 최적화 가능하다.