프로그래머스 Level2 - 피보나치 수 C++

간단하게 DP로 풀었다.

피보나치는

F(0) = 0,

F(1) = 1,

F(2) = 0+1 = F(0)+F(1) = 1,

F(3) = F(1)+F(2) = 2

이런식으로 n까지 구해주면 된다.

 

재귀를 사용해도 되지만 재귀를 사용할 경우 이전에 계산했던 것을 또 다시 계산하는 불필요한 일들이 일어나므로,

배열을 사용하면 훨씬 효율이 좋게 답을 얻을 수 있다.

#include <string>
#include <vector>
 
using namespace std;
int arr[100001];
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;
}