Lesson 13. Fibonacci numbers - FibFrog #2 (속도 개선)

1. 속도 개선 아이디어

예외처리를 추가해서 재귀 호출을 줄여볼 수 있다.

만약 현재까지 점프수가 최소 점프수와 같다면? 더이상 진행할 필요가 없다.

 

2. 코드 (C++)

//Count the minimum number of jumps to the other side of a river
void Calculate(int cur_pos, int cur_jump, int& min_jump, vector<int>& fib, vector<int>& leaves)
{
    //added a base case 
    if(cur_jump >= min_jump) return;

    //arrived at the destination
    if(leaves[cur_pos] == leaves.back())
    {
        if(cur_jump < min_jump) min_jump = cur_jump;
        return;
    }

    //find a leaf to jump on
    for(size_t i = cur_pos + 1; i < leaves.size(); i++)
    {
        //The leaf to jump on should be at a distance of a Fibonacci number
        auto it = find(fib.begin() + 2, fib.end(), leaves[i] - leaves[cur_pos]);
        if(it == fib.end()) continue;

        Calculate(i, cur_jump + 1, min_jump, fib, leaves);
    }
}

int solution(vector<int> &A) {

    int destination = A.size() + 1;

    //generate fibonacci numbers
    vector<int> fib = {};
    fib.emplace_back(0);
    fib.emplace_back(1);
    int M = 2;
    int n = fib[1] + fib[0];
    while(n <= destination)
    {
        fib.emplace_back(n);
        M++;
        n = fib[M - 1] + fib[M - 2];
    }

    //generate leaves vector that contains only the leaves that can be jumped to
    vector<int> leaves = {};
    leaves.emplace_back(0);
    for(size_t i = 0; i < A.size(); i++)
    {
        if(A[i] == 1) leaves.emplace_back(i + 1);
    }
    leaves.emplace_back(destination);

    //Count the minimum number of jumps to the other side of a river
    int min_jump = numeric_limits<int>::max();
    for(size_t i = 1; i < leaves.size(); i++)
    {
        auto it = find(fib.begin() + 2, fib.end(), leaves[i]);
        if(it == fib.end()) continue;
        Calculate(i, 1, min_jump, fib, leaves);
    }

    if(min_jump == numeric_limits<int>::max()) return -1;
    return min_jump;
}

 

 

3. 결과