[백준] 108710 피보나치 수 5 - DP JAVA

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

10870번: 피보나치 수 5

코드설명

DP 문제입니다.

 

DP를 더 활용하기 위한 방식으로는 배열을 활용하여 진행합니다.

1. 배열을 활용한 방식

2. 재귀를 활용한 방식

 

위의 2가지 방식으로 구현할 수 있습니다.

 

피보나치의 점화식은 fibo(N) = fibo(N-1) + fibo(N-2) 입니다.

 

유의할점은, 배열로 구현할시에는

N의 값의 범우가 0부터 20까지 이므로 0일경우를 유의해서 코딩해야합니다. (그렇지않으면, 100%에서 ArrayIndexOutOfException Error가 뜹니다. )

 

 

코드

 

 

 

미리 N이 20 일떄까지 모두 구해놓은 DP 코드입니다.

dp[0] ~ dp[20] 까지 미리 다 구해놓아서 작동하는 방식으로 코드를 구현했습니다.

또한 피보나치 수를 배열로 구하고 있습니다.

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

public class Main {
	public static int N;
	public static int[] dp;
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	
    	dp = new int[21];
    	dp[0] = 0;
    	dp[1] = 1;
    	
    	fibonacci(2);
    	
    	System.out.println(dp[N]);
    }
    
    public static void fibonacci(int idx) {

    	if(idx == 21) {
    		return ;
    	}
    	
    	dp[idx] = dp[idx-1] + dp[idx-2];
    	fibonacci(idx + 1);
    	
    }
}

 

재귀를 활용한 방식입니다.

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

public class Main {
	public static int N;
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());

    	fibonacci(2);
    	
    	System.out.println(fibonacci(N));
    }
    
    public static int fibonacci(int idx) {
    	if( idx == 0)
    		return 0;
    	if( idx == 1)
    		return 1;
    	
    	return fibonacci(idx - 1) + fibonacci(idx - 2);
    	
    }
    
}