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

www.acmicpc.net/problem/2748

2748번: 피보나치 수 2

fibo[91]를 사용해 중복된 계산을 하지 않도록 했다.

 

코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

long long fibo[91];

long long Solve(int n)
{
	long long& ret = fibo[n];

	//계산한 적이 있을때
	if (ret != -1)
		return ret;

	ret = Solve(n - 1) + Solve(n - 2);

	return ret;
}

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

	int n;

	memset(fibo, -1, sizeof(fibo));

	//0번째 피보나치 수와 1번째 피보나치 수는 저장해 놓는다
	fibo[0] = 0;
	fibo[1] = 1;

	cin >> n;

	cout << Solve(n);

	return 0;
}