[BOJ] 2748. 피보나치 수 2

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

2748번: 피보나치 수 2

n번째 피보나치 수를 배열에 저장해놓는다.

그러면 n번째까지의 피보나치 수를 구하는데 O(n)이 걸리고 그 이후로 접근할 때는 O(1)이면 바로 접근 가능하다.

 

i번째 피보나치 수 = i-1번째 피보나치 수 + i-2번째 피보나치 수

0번째와 1번째를 미리 넣어놓고 이 점화식을 이용하면 모든 피보나치수를 구할 수 있다.

 

#include <iostream>
using namespace std;
 
long long pibo[91];
 
int main()
{
 
    int n;
    cin >> n;
 
    pibo[0] = 0;
    pibo[1] = 1;
 
    for (int i = 2; i <= 90; i++) {
        pibo[i] = pibo[i - 1] + pibo[i - 2];
    }
 
    cout << pibo[n];
 
    return 0;
}