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

programmers.co.kr/learn/courses/30/lessons/12945

코딩테스트 연습 - 피보나치 수

 

#include <string>
#include <vector>
#include <cstring>
using namespace std;

int dp[100001];

int F(int n) {
    if(dp[n] != -1) return dp[n];
    if(n == 0) return 0;
    if(n == 1) return 1;
    return dp[n] = F(n - 1) % 1234567 + F(n - 2) % 1234567;
}

int solution(int n) {
    memset(dp, -1, sizeof(dp));
    return F(n) % 1234567;
}