[BOJ][Java] 2747번 - 피보나치 수

문제

백준 2747번 문제: 피보나치 수

피보나치 수 시리즈 문제 풀이

• 2747번. 피보나치 수 1
• 2748번. 피보나치 수 2
• 2749번. 피보나치 수 3
• 10826번. 피보나치 수 4
• 10870번. 피보나치 수 5

문제 설명

동적 계획법으로 피보나치 수를 계산하는 문제
n이 45까지 주어진다.
최대 45까지이므로 배열을 만들 때 int형으로 만들어도 숫자 저장이 가능하다.
1번째와 2번째 값, 즉 n의 값이 0이나 1일 때는 초기값인 0과 1을 반환해야 한다.
n이 2 이상일 경우에는 피보나치의 식Fn = Fn-1 + Fn-2을 따라 배열에 저장해 주면 된다.

처음에는 재귀함수로 풀려고 시도했지만 시간 초과가 떠서 재귀로는 풀지 못했다.

성공 코드

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

public class Main {

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


        bw.write(String.valueOf(fibonacchi(n)));
        bw.close();
    }

    public static int fibonacchi(int n) {
        int nums[] = new int[n+1];

        for (int i = 0; i <= n; i++) {
            nums[i] = (i < 2)? i : nums[i-1]+nums[i-2];
        }

        return nums[n];
    }
}