[백준] 17175 피보나치는 지겨웡~ - 동적계획법(DP, Dynamic Programming) JAVA

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

코드설명

동적계획법(DP, Dynamic Programming) 문제입니다.

 

N이 50 까지 오르면, fibonacci의 점화식에 의해 2^50 까지의 시간복잡도입니다.

그러므로 Cache를 활용해 연산된 데이터는 중복연산하지 않습니다.

코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
    private static int N, K, M, L;
    private static int[] arr;
    private static long answer = 0;
    private static int[] cache;
    private static final int MOD = 1000000007;
    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());
		cache = new int[51];
		Arrays.fill(cache, -1);
		System.out.println(fibo(N) + 1);
    }
    
    static int fibo(int n) {
    	if(n == 0 || n == 1) {
    		return 0;
    	}
    	if(cache[n] != -1) return cache[n];
    	return cache[n] = (fibo(n-1) + fibo(n-2) + 2) % MOD;
    }
    
    
}