[백준 2747] 피보나치 수

출처 : https://www.acmicpc.net/problem/2747

유명한 피보나치입니다..

사실 피보나치 문제 종류가 많길래 첫번째 문제는 

기본적인 재귀를 푸는걸로 예상하고 풀엇더니 바로 시간초과가 발생햇어용

그래서 동적계획법을 사용했습니당.

 

 

public class Q2747 {
	static int[] arr;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		arr = new int[n+1];
		arr[0] = 0;
		arr[1] = 1;
		Q2747 q = new Q2747();
		int result = q.fib(n+1);
		System.out.println(result);
	}
	public int fib(int n) {
		if(n==1 || n==2) {
			return arr[n-1];
		}else if(arr[n-1] > 0) {
			return arr[n-1];
		}else {
			arr[n-1] = fib(n-1) + fib(n-2);
			return arr[n-1];
		}
	}
}