백준 2748 피보나치수2 [c++]

#include <iostream>
using namespace std;

long long arr[90] = { 0,};	//n이 90까지 입력될 수 있기때문에 long long 으로 선언해야 한다.

long long func(int n)	//재귀함수를 사용하여 피보나치수를 구하고 구한 피보나치 수를 배열에 저장한다.
{
	if (n == 0 || n == 1)
		return arr[n];
	else if (arr[n] == 0)
		 arr[n] = func(n - 1) + func(n - 2);

	return arr[n];
}

int main()
{	
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;

	arr[0] = 0;	//0번째 피보나치수는 0
	arr[1] = 1;	//1번째 피보나치수는 1

	cout << func(n);

	return 0;
}