[백준/JAVA] 24416번: 알고리즘 수업 - 피보나치 수 1

🔺 문제

 

24416번: 알고리즘 수업 - 피보나치 수 1

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int n;
    static int cnt, dpCnt = 0;
    static int[] f;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        f = new int[n+1];
        
        fib(n);
        fibonacci(n);
        
        System.out.println(cnt + " " + dpCnt);
    }
    
    // 재귀
    static int fib(int num) {
        if(num == 1 || num == 2) {
            cnt++;
            return 1;
        }
        return fib(num - 1) + fib(num - 2);
    }
    
    // DP
    static int fibonacci(int num) {
        f[1] = f[2] = 1;
        for(int i = 3 ; i <= num ; i++) {
            f[i] = f[i - 1] + f[i - 2];
            dpCnt++;
        }
        return f[num];
    }
}

✅ 해결 아이디어
✔ 문제에 나온 의사코드 그대로... ( 재귀 &  DP)

 

 

---

💬 느낀 점

DP 단계별로 첨부터 다시 밟아보려고 한다...

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[백준] 24416 / 알고리즘 수업 - 피보나치 수 1