[Codility] Fib Frog

 

[Codility] Fib Frog

 

---

 

해결전략

 

피보나치 Fibonacci

다이나믹 프로그래밍 Dynamic Programming

---

 

정답코드

 

#include <algorithm>
#include <vector>
using namespace std;

const int INT_MAX = 2147000000;

vector<int> fib;

void Fibonacci(int k)
{
    fib.push_back(0);
    fib.push_back(1);

    while (fib.back() < k) {
        fib.push_back(fib.end()[-1] + fib.end()[-2]);
    }
}

int solution(vector<int> &A) {
    int n = A.size();
    
    A.insert(A.begin(), 1); // 개구리가 시작하는 강둑
    A.push_back(1); 		// 개구리가 도착하는 강둑

    Fibonacci(n+2);
   
    vector<int> jumps(n+2, -1);
    jumps[0] = 0;

    for (int i = 1; i < n+2; i++) // 각 위치에서의 최소 점프를 구하기
    {
        if (A[i] == 0) continue;

        int min_jump = INT_MAX;
        for (const auto& iter : fib) 
        {
            if (iter > i) break;

            if (jumps[i-iter] != -1) {
                min_jump = min(min_jump, jumps[i-iter] + 1);
            }
        }

        if (min_jump != INT_MAX) {
            jumps[i] = min_jump;
        }
    }

    return jumps[n+1];
}

 

 

#include <algorithm>
#include <vector>
using namespace std;

const int INT_MAX = 2147000000;

vector<int> fib;

// 피보나치 수열을 생성하는 함수
void Fibonacci(int k)
{
    fib.push_back(0);
    fib.push_back(1);

    while (fib.back() < k) { // 피보나치 수열의 마지막 값이 k보다 작을 때까지 계속 생성
        fib.push_back(fib.end()[-1] + fib.end()[-2]);
    }
}

int solution(vector<int> &A) {
    int n = A.size();
    
    A.insert(A.begin(), 1); // 개구리가 시작하는 강둑
    A.push_back(1); // 개구리가 도착하는 강둑
    
    Fibonacci(n+2); // 피보나치 수열 생성
   
    vector<int> jumps(n+2, -1); // 각 위치에 도달하는데 필요한 최소 점프 횟수를 저장할 벡터 -1 초기화
    jumps[0] = 0; // 시작점에서의 점프 횟수는 0
   
    for (int i = 1; i < n+2; i++) // 각 위치에서의 최소 점프를 구하기
    {
        if (A[i] == 0) continue; // 잎이 없는 위치는 건너뛰기

        int min_jump = INT_MAX;

        for (int j = 0; j < fib.size(); j++) // 가능한 모든 피보나치 점프를 시도
        {
            if (fib[j] > i) break; // 현재 위치보다 큰 점프는 무시

            if (jumps[i-fib[j]] != -1) { // 이전 위치에서 점프가 가능한 경우, 최소 점프 횟수를 업데이트
                min_jump = min(min_jump, jumps[i-fib[j]] + 1);
            }
        }

        if (min_jump != INT_MAX) { // 최소 점프 횟수가 업데이트된 경우, 해당 위치에 저장
            jumps[i] = min_jump;
        }
    }

    return jumps[n+1]; // 마지막 위치에 도달하는데 필요한 최소 점프 횟수 반환
}

 

---