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

문제 정보

• 백준 브론즈 1
• DP
• 문제 링크

풀이

피보나치 수를 구하는 함수를 재귀 방식과 DP 방식 각각으로 구현하면 되는 문제다.

추가로, DP 방식으로 구현할 때 길이 n의 배열을 사용했는데 사실 길이 2의 배열로도 계산할 수 있다. 피보나치 수의 점화식 f(n) = f(n - 1) + f(n - 2)에서 현재 값을 구하는 데 직전 2개의 값만 필요하기 때문이다.

int[] dp = new int[2];
dp[0] = 0;
dp[1] = 1;
 
for (int i = 2; i <= n; i++) {
    int next = dp[0] + dp[1];
    dp[0] = dp[1];
    dp[1] = next;
}
 
return dp[1];

코드

import java.io.*;
import java.util.*;
 
public class Main
{
    private static int code1Cnt;
    private static int code2Cnt;
    public static void main(String[] args) throws IOException {
        code1Cnt = code2Cnt = 0;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        
        fib(n);
        fib_DP(n);
        
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        bw.write(code1Cnt + " " + code2Cnt + "\n");
        bw.flush();
        bw.close();
    }
    
    private static int fib(int n) {
        if (n == 1 || n == 2) {
            code1Cnt++;
            return 1;
        }
        return fib(n - 1) + fib(n - 2);
    }
    
    private static int fib_DP(int n) {
        int[] dp = new int[n + 1];
        dp[1] = dp[2] = 1;
        
        for (int i = 3; i <= n; i++) {
            code2Cnt++;
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[n];
    }
}