[백준] 🥉 2748 피보나치 수 2

📌 난이도

🥉 Bronze 1

📌 문제

https://www.acmicpc.net/problem/2748

📌 풀이

문제 자체는 정말 간단하다.
재귀를 사용해서 풀어도 되는 문제이지만, 이 문제는 피보나치2라 시간제한이 1초밖에 안되서 재귀같은 시간복잡도가 높은 알고리즘으로 풀면 제한시간에 걸리게된다.
따라서 DP알고리즘을 사용하여 해결하여야 제한시간내에 풀 수 있게된다.

나는 다음과 같이 Bottom-Up 방식을 사용하였다.

📌 Code

package DP;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class N2748 {
    public static long[] fibo;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int count = Integer.parseInt(st.nextToken());
        fibo = new long[count+1];
        Arrays.fill(fibo, -1);

        fibo[0] = 0;
        if(count != 0) {
            fibo[1] = 1;
            for (int i = 2; i < count + 1; i++) {
                MakeFibo(i);
            }
        }
        System.out.println(fibo[count]);

    }
    public static void MakeFibo(int i){
        if(fibo[i]==-1) {
            fibo[i] = fibo[i - 1] + fibo[i - 2];
        }
    }
}

package (이름); 를 때고, class 이름을 Main으로 변경하면 된다.

---

개인 공부 기록용 블로그입니다.
틀리거나 오류가 있을 경우 제보해주시면 감사하겠습니다.😁