[Programmers] Level2 : 피보나치 수

Question

---

Solution

• 점화식 f(n) = f(n-1) + f(n-2) 를 재귀를 통하여 구현하되,
  Dp/memoization 알고리즘을 활용해야 시간초과가 나지 않는다.

---

Cord

#include <string>
#include <vector>

using namespace std;

int dp[100001];

int fibonacci(int n)
{
    if (n == 0) { return 0; }
    else if (n == 1) { return 1;}
     
    // dp[n]에 기록된 데이터가 있으면 꺼내기
    if (dp[n] != 0) { return dp[n]; }
     
    // 결과 값을 dp[]에 저장
    return dp[n] = (fibonacci(n-1) + fibonacci(n-2)) % 1234567;
}

int solution(int n) 
{
    int answer = fibonacci(n);
    return answer;
}

---

Result