문제접근
•
일반 재귀로 풀면 제한시간내에 풀 수 없기 때문에 메모이제이션을 사용해야함
놓쳤던 부분
•
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);
}
C++
복사