[백준 2748번] 피보나치 수 2

문제 링크: 2748번 피보나치 수 2

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

 

이미 계산한 값은 저장하는, memoization을 적극적으로 활용한다.

 

import java.util.Scanner;

public class Main {
	static int MAX = 90;
	
	public static long fibo(int n) {
		long[] arr = new long[MAX+1];
		arr[0]=0; arr[1]=1; arr[2]=1;
		for (int i = 3; i <= n; i++) {
			arr[i] = arr[i-1]+arr[i-2];
		}
		return arr[n];
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		long res = fibo(n);
		System.out.println(res);
		
		sc.close();		
	}
}