프로그래머스 Lv2 피보나치 수

이 문제는 피보나치 수열을 구하면된다.

재귀적으로 푸는데, 이미 계산한 피보나치수는 다시 계산을 하지 않도록 하는 것이 중요하다.

#include <string>
#include <vector>

using namespace std;
long long arr[100'001];

long long fibonacci(int n)
{
    if(n == 1)
    {
        return 1;
    }
    
    if(n == 2)
    {
        return 1;
    }
    
    if(arr[n] == 0)
    {
        arr[n] = fibonacci(n - 1) + fibonacci(n - 2);
        return arr[n];
    }
    return arr[n];
}
int solution(int n) {
    long long answer = 0;
    answer = fibonacci(n);
    return answer;
}