Project Euler #2 - Even Fibonacci numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

출처: https://projecteuler.net/

파보나치 수열 중 짝수이면서 4백만 이하인 모든 항을 더하는 문제입니다.

쉬운 문제이지만 memoization 으로 시간 복잡도를 줄여봤습니다.

my solving

c++

#include <iostream>
#include <map>
#include <ctime>
 
using namespace std;
 
const int limit = 4000000;
 
map<int, int> cache;
int recursive(int num)
{
    map<int, int>::iterator it = cache.find(num);
    if (it != cache.end())
        return it->second;
 
    int ret = 0;
    if (num == 0)
        ret = 0;
    else if (num == 1)
        ret = 1;
    else
        ret = recursive(num - 1) + recursive(num - 2);
 
    cache.insert(make_pair(num, ret));
 
    return ret;
}
 
int main() 
{
    int ret = 0;
    int num = 0;
    int i = 0;
 
    while (true)
    {
        num = recursive(i);
 
        if (num > limit)
            break;
 
        if (num % 2 == 0)
            ret += num;
 
        i++;
    }
 
    cout << ret << endl;
 
    system("pause");
    return 0;
}