백준 24416 java - 피보나치 수1(동적계획법/DP)

문제, 입출력, 테스트케이스

백준 단계별로 풀기에서 동적계획법1이 all solve이었는데 갑자기 한 문제가 추가 되어서 풀게 된 문제이다.

 

브론즈 1이지만 DP의 효율성을 알 게 해주는 아주 귀중한 문제이다.

수도 코드가 이미 있어서 따라 치기만 해도 된다.

 

package 동적계획법;

import java.util.*;
import java.io.*;

public class Boj_24416_알고리즘수업_피보나치 {
	static int a, b, dp[];
	public static void main(String[] args) throws Exception{
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		dp = new int[n+1];
		dp[1] = 1;
		dp[2] = 1;
		fib(n);
		
		fibonacci(n);
		
		System.out.print(a + " " + b);
		
	}
	private static int fibonacci(int n) {
		for (int i = 3; i <= n; i++) {
			dp[i] = dp[i-1] + dp[i-2]; 
			b++;
		}
		return dp[n];
	}
	private static int fib(int n) {
		if(n == 1 || n == 2) {
			a++;
			return 1;
		}
		
		return fib(n-1) + fib(n-2);
	}
}

이제 25단계까지 3문제 남았다!!!