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

1. 속도 개선 아이디어

leaves를 역방향으로 탐색하는 건 어떨까? 

시작 점프(starting point)를 최대한 큰 피보나치 수로 시작하면,

도착지에 더 적은 점프로 도착할 확률 높지 않을까? 

 

최소 점프를 일찍 구하게 되면, 점프 예외처리(cur_jump + 1 >= min_jump)를 통해, 처리 속도를 높일 수 있다.

최소 점프가 아니더라도, 낮은 수의 점프를 일찍 구하게 되면, 속도 개선에 도움이 된다.

 

2. 코드 (C++)

#include <queue>

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)
    {
        if(n == destination) return 1;
        fib.emplace_back(n);
        M++;
        n = fib[M - 1] + fib[M - 2];
    }

    //generate a leaves vector that contains the starting point
    vector<int> leaves = A;
    leaves.insert(leaves.begin(), 1);
    //leaves.emplace_back(1);
    
    //Count the minimum number of jumps to the other side of a river
    queue<pair<int, int>> q = {}; // queue<current position, current jump>
    int min_jump = numeric_limits<int>::max();
    //for(size_t i = 1; i < leaves.size(); i++)
    for(int i = leaves.size() - 1; i > 0; i--)
    {
        if(leaves[i] == 0) continue;

        auto it = find(fib.begin() + 2, fib.end(), i);
        if(it == fib.end()) continue;

        q.push({i, 1});
        while(!q.empty())
        {
            int cur_pos = q.front().first;
            int cur_jump = q.front().second;
            q.pop();

            if(cur_jump + 1 >= min_jump) continue;

            //arrived at the destination
            it = find(fib.begin() + 2, fib.end(), destination - cur_pos);
            if(it != fib.end())
            {
                min_jump = cur_jump + 1;
                continue;
            }

            //find a leaf to jump on
            for(size_t k = 2; k < fib.size(); k++)
            {
                //The leaf to jump on should be at a distance of a Fibonacci number
                int next_leaf = cur_pos + fib[k];
                if(next_leaf >= destination) break;
                if(leaves[next_leaf] == 0) continue;

                q.push({next_leaf, cur_jump + 1});
            }
        }
    }

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

 

3. 결과