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

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

 

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

 

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

 

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

 

입력

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

 

출력

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

 

전체 코드(Java)

import java.io.*;
import java.math.BigInteger;

class Main {
    public static void main(String[] args) throws IOException {
        BigInteger[] arr = new BigInteger[91];

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        arr[0] = BigInteger.valueOf(0);
        arr[1] = BigInteger.valueOf(1);

        for (int i = 2; i <= n; i++) {
            arr[i] = arr[i - 1].add(arr[i - 2]);
        }

        System.out.println(arr[n]);
    }
}

 

풀이

간단하게 DP(Dynamic Programming)을 이용하여 풀이하였다.

• 풀이 원리는 메모이제이션(memoization)의 기본 활용으로, 피보나치 수열의 값은 이전 두 항의 값으로 결정된다.
• 이러한 원리를 이용하여 연산 값을 별도의 배열에 저장하여 다음 계산에 활용하였다.
• 일반적인 재귀 함수를 통해 피보나치 수를 구하면 시간 초과가 발생한다. 따라서 for 문을 이용하여 풀이하였다.
• n이 90일 때 최대값이 long의 범위 안에 있으므로, long을 활용할 수 있지만, 더 큰 값에 대한 계산과 응용을 고려하여 BigInteger를 사용해보았다.

초기의 두 항이 결정되면, 나머지 항은 for 문을 통해 채울 수 있게 된다.

따라서 arr의 0번째, 1번째 인덱스를 할당해주고 for 문에서 입력한 n까지의 배열을 모두 채운 뒤, n번 인덱스를 출력하면 된다.