백준 24416

문제

Code

package test;

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

public class P24416 {
	static int cnt = 0; // 일반 재귀로 계산할 때 계산 횟수
    static int dpCnt = 0; // dp와 재귀 함께 계산할 때 계산 횟수
    
	static int[] dp;
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		dp = new int[n];
        
		fib(n);
		fib_dp(n);
        
		System.out.println(cnt);
		System.out.println(dpCnt);
		

	}
    
    // 일반 재귀로 계산한 피보나치 수열
	private static int fib(int n) {
		if(n == 1 || n == 2) {
			cnt++;
			return 1;
		}
		return fib(n - 1) + fib(n - 2);
	}
	
    // dp와 재귀로 함께 계산한 피보나치 수열
	private static int fib_dp(int n) {
		dp[0] = 1;
		dp[1] = 1;
		
		for(int i = 2; i < n; i++) {
			dpCnt++;
			dp[i] = dp[i - 1] + dp[i - 2];
		}
		return dp[n - 1];
	}

}