[Baekjoon Online Judge] 2748번: 피보나치 수 2

2748번: 피보나치 수 2

요구사항

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

입력

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

출력

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

---

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

public class Baekjoon2748 {

    static long[] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(bufferedReader.readLine());

        dp = new long[n + 1];

        for (int i = 0; i <= n; i++) {
            fibonacci(i);
        }

        bufferedWriter.write(String.valueOf(dp[n]));

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }

    private static void fibonacci(int i) {
        if (i == 0) {
            dp[i] = 0;
        } else if (i == 1) {
            dp[i] = 1;
        } else {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
    }
}

 

 아주 기본적인 다이나믹 프로그래밍을 활용한 피보나치 수를 출력하는 문제이다. 한가지 고려해야 할 점은 입력 조건에 n이 90보다 작거나 같은 자연수 이다. 만약 dp 테이블의 데이터 타입을 int로 잡을 경우, int가 표현할 수 있는 범위를 넘어서기 때문에 그보다 큰 long 타입으로 선언해야 한다. 

 

 항상 알고리즘 문제를 해결할 때 최악의 상황을 꼭 테스트 케이스로 확인하는 습관을 들여야 겠다.