[C++] 프로그래머스 Level 2 : 피보나치 수

#include <string>
#include <vector>

using namespace std;

int arr[100001] = {0}; // dp를 위한

int solution(int n) {
    int answer = 0;
    
    arr[0] = 0; arr[1] = 1;
    
    for(int i = 2; i <= n; i++){
        arr[i] = (arr[i-2] + arr[i-1]) % 1234567;
    }
    
    answer = arr[n];
    
    return answer;
}

피보나치 구하기는 재귀함수 호출 또는 dp 로 문제를 풀 수 있다.

그래서 처음에는 간단한 재귀함수로 문제를 풀었는데 역시나 시간초과

#include <string>
#include <vector>

using namespace std;

int fib(int n){
    if(n == 0){
        return 0;
    } else if(n == 1){
        return 1;
    } else {
        return (fib(n-2) + fib(n-1)) % 1234567;
    }
}

int solution(int n) {
    int answer = 0;
    
    answer = fib(n);
    
    return answer;
}

dp로 구하는 것이 맞다.