[백준]2748_피보나치 수 2

https://www.acmicpc.net/problem/2748

Solved

✔ 재귀 호출로 구현한다면 시간 복잡도가 시간 복잡도의 경우 2^n이므로 최악의 경우 2^90가 나온다. 그러니 피보나치 수는 어지간하면 DP 쓰자

using namespace std;
#include <iostream>

long long fib[91];

int main() {
	int n;
	cin >> n;
	fib[1] = 1;
	for (int i = 2; i <= n; i++)
		fib[i] = fib[i - 2] + fib[i - 1];
	cout << fib[n] << '\n';
	return 0;
}