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

1. 속도 개선 아이디어

여전히 bad_alloc이 해결되지 않았다.

결국 q.push 횟수를 줄여야 한다.

 

현재 q.push는 start_leaf 와 next_leaf에서 발생한다.

결국 내가 점프할 leaf가 있냐 없느냐가 q.push 발생 여부를 결정한다. 

그럼 어떻게 하면 q.push를 줄일 수 있을까?

 

다음과 같은 경우를 생각해보자.

 

파란색과 빨간색은 어느 한 지점에서 만나는데, 파란색은 2번의 점프로, 빨간색은 1번의 점프로 도착했다.

우리는 피보나치라는 정해진 크기로만 점프할 수 있기 때문에, 이 후 점프(녹색)는 같을 수 밖에 없다.

 

따라서 우리에게는 점프 관리가 필요하다.

만약 파란색이 A지점에 도착했을 때, 이미 빨간색이 1번의 점프로 도착한 사실을 알 수 있다면, 파란색은 더이상 진행할 필요가 없다.

 

혹은 A지점에서는, 도착지에 도달할 수 없다는 사실을 알고 있다면? 

A지점을 거쳐가는 경로는 계산할 필요가 없을 것이다.

 

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);

    vector<int> jump_record(leaves.size(), numeric_limits<int>::max());
    
    //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();
            
            //this position(leaf) cannot reach the destination or
            //has already arrived here with fewer jumps
            if(jump_record[cur_pos] == -1) continue;
            else if(cur_jump >= jump_record[cur_pos]) continue;
            else jump_record[cur_pos] = cur_jump;

            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
            bool invalid_leaf = true;
            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] == 1)
                {
                    invalid_leaf = false;
                    q.push({next_leaf, cur_jump + 1});
                }
            }

            //this position(leaf) cannot reach the destination
            if(invalid_leaf) jump_record[cur_pos] = -1;
        }
    }

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

 

 

3. 결과