BOJ 2747 - 피보나치 수

문제

BOJ 2747 - 피보나치 수

피보나치 수는 0과 1로 시작하며, 다음 피보나치 수는 바로 앞 두 피보나치 수의 합이 된다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 45보다 작거나 같은 자연수이다.

출력

n번째 피보나치 수를 출력한다.

예제

입력:

10

출력:

55

풀이

핵심 아이디어: 피보나치 수는 점화식 F(n) = F(n-1) + F(n-2)를 직접 반복문으로 계산한다. N ≤ 45이므로 공간 최적화를 위해 배열 대신 변수 세 개만 사용한다.

1. 초기값 설정: F1 = 0(F(0)), F2 = 1(F(1)), F3 = 1(F(2))
2. 반복 계산: i = 2부터 N까지 F3 = F1 + F2, F1 = F2, F2 = F3을 반복한다.
3. 예외 처리: N = 1인 경우 루프가 실행되지 않으므로 초기값 F3 = 1이 반환된다.
4. 공간 최적화: 배열 없이 변수 3개만으로 O(1) 공간에서 계산한다.

코드

package day349;
 
import java.util.Scanner;
 
public class Day300BOJ2747피보나치 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int F1 = 0, F2 = 1, F3 = 1;
        for (int i = 2; i <= N; i++) {
            F3 = F1 + F2;
            F1 = F2;
            F2 = F3;
        }
        System.out.println(F3);
        sc.close();
    }
}

복잡도

• 시간: O(N) — N번의 반복
• 공간: O(1) — 변수 3개만 사용