2748번: 피보나치 수 2

문제접근🤔

• 일반 재귀로 풀면 제한시간내에 풀 수 없기 때문에 메모이제이션을 사용해야함

놓쳤던 부분😅

• fibo와 mem 계산과정에서 int 자료형 범위를 넘을 수 있기 때문에 자료형을 long long으로 해줘야함

코드😁

2020 KB

0 ms

#include <iostream>
using namespace std;

long long mem[91];

long long fibo(int n)
{
	if (n == 0)
		return (0);
	if (n == 1 || n == 2)
		return (1);
	if (mem[n] != 0)
		return (mem[n]);
	mem[n] = fibo(n - 1) + fibo(n - 2);
	return (mem[n]);
}

int main(void)
{
	int n;

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;

	cout << fibo(n);

	return (0);
}