백준 2748 피보나치 수 2 JAVA 풀이 (DP, 반복문, 시간복잡도)

🔗 문제 링크

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

---

📌 문제 개요

피보나치 수열에서 N번째 값을 구하는 문제이다.
피보나치 수열은 다음과 같은 규칙을 가진다.

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

N의 범위가 최대 90이므로 일반적인 재귀 방식은 비효율적

---

📌 접근 방법

피보나치 수는 이전 두 값을 이용해 계산할 수 있으므로
배열 대신 두 개의 변수만 사용해서 해결할 수 있다.

 

또한 반복문을 사용하면 시간복잡도를 O(N)으로 줄일 수 있다.

---

📌 핵심 아이디어

• 피보나치는 이전 값 2개만 알면 계산 가능
• 매 반복마다 값 이동이 중요하다
• temp = one + two
  one = two
  two = temp

   
• N ≤ 90 이므로 long 타입 사용 가능

---

📌 전체 코드

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

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());

        long one = 0;
        long two = 1;

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

        for(int i = 1; i < N; i++){
            long t = one + two;
            one = two;
            two = t;
        }

        System.out.println(two);
    }
}

📄 정리

• 피보나치는 DP의 가장 기본적인 문제
• 배열 없이 변수 2개로 최적화 가능
• 자료형 범위(long)만 신경 쓰면 쉽게 해결 가능