[백준] 2748번: 피보나치 수 2 (Java)

1. 문제설명

0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 2번째 부터는 다음 점화식을 만족한다.

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

n이 주어졌을 때, n번째 피보나치 수를 구하는 문제이다. 

• 시간 제한: 1초
• 메모리 제한: 128MB

 

2. 접근 방식

DP - Bottom-Up 방식

• 0, 1번째 피보나치 수를 먼저 계산하고 배열에 저장한다.
• 반복문을 통해 2~n번째 피보나치 수를 순차적으로 계산하고 저장한다.
• 배열의 n번째 값을 반환한다.

DP - Top-Down 방식

• 재귀 호출을 통해 n-1, n-2번째 피보나치 수를 계산하고, 두 값을 더해 배열[n]에 저장한다.
• 배열의 n번째 값을 반환한다.

 

3. 틀린 이유

피보나치 수를 저장하는 배열의 타입을 int로 선언했다.

예를 들어 n이 90이면 정답이 2880067194370816120로 int 범위를 넘어가기 때문에 long으로 변경했다.

 

 

4. 최종 코드

import java.io.*;

public class Main {
    static int n; // n번쨰 피보나치 수 구하기
    static long[] arr1; // bottom up 방식에 사용할 배열
//    static long[] arr2; // top down 방식에 사용할 배열

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

        arr1 = new long[n+1];
        System.out.println(bottomUp(n));

//        arr2 = new int[n+1];
//        System.out.println(topDown(n));
    }

    static long bottomUp(int n) {
        // n이 0이면, 0번째 피보나치 수를 반환
        if(n == 0) return arr1[0] = 0;

        // 초기값 설정
        arr1[0] = 0; arr1[1] = 1;

        // 2부터 n까지의 피보나치 수를 반복문을 통해 계산
        for(int i=2; i<=n; i++) {
            arr1[i] = arr1[i-1] + arr1[i-2];
        }
        
        return arr1[n]; // n번째 피보나치 수 반환
    }

//    static long topDown(int n) {
//        // n이 0 또는 1이면, 해당 값을 반환
//        if(n < 2) return arr2[n] = n;
//        // 이미 계산된 값이 있으면, 그 값을 반환
//        if(arr2[n] > 0) return arr2[n];
//
//        // 계산되지 않은 경우, 재귀 호출로 값을 계산하여 저장
//        arr2[n] = topDown(n-1) + topDown(n-2);
//        return arr2[n]; // n번째 피보나치 수 반환
//    }
}