2748 피보나치수

#include <iostream>

using namespace std;

unsigned long long int arr[100];

unsigned long long int fib(int a) {
	if (a == 1) return arr[a] = 1;
	if (a == 2) return arr[a] = 1;
	if (arr[a] != 0) return arr[a];
	return arr[a] = fib(a-1) + fib(a-2);
}

int main() {
	int test = 0;
	cin >> test;
	cout << fib(test) << endl;
	return 0;
}

메모이제이션 기법을 이용하여 해결, 배열에 이전값을 저장하여, 해당 배열을 호출할때, 값이 0 (기록되어있지 않으면) 인경우 이전값과, 이전이전의 값을 더하여 배열에 저장, 값이 0이 아니면(값이 기록되어있으면) 해당배열의 값을 출력. 이러한 원리로 구현했고, 47정도 값을 넘어가면 int로 표현이 불가하기에, unsigned long long int 형을 사용하여 구현.