Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 코인 경로(Coin Path) 문제: 최소 비용 점프 경로 찾기

문제 이해

배열 A(인덱스는 1부터 시작)에 N개의 숫자 A1, A2, ..., AN이 들어 있고, 또 하나의 정수 B가 주어진다고 가정해 봅시다. 정수 B는 배열 A의 임의의 인덱스 i에서 i+1, i+2, ..., i+B 범위 안의 위치로 점프할 수 있음을 의미합니다. 또한 인덱스 i를 밟으면 Ai만큼의 코인을 지불해야 하며, Ai가 -1이라면 해당 위치로는 점프할 수 없습니다.

목표는 배열 A의 인덱스 1에서 출발하여 최소한의 코인으로 인덱스 N에 도달하는 것입니다. 우리는 최소 비용으로 인덱스 N까지 도달하기 위해 거쳐야 할 인덱스 경로(1부터 N까지)를 반환해야 합니다. 만약 비용이 같은 경로가 여러 개 존재한다면 그중 사전순으로 가장 작은 경로를 찾아야 하며, 인덱스 N에 도달할 방법이 전혀 없다면 빈 배열을 반환하면 됩니다.

예를 들어 입력이 [1,2,4,-1,2], 2라면 출력은 [1,3,5]가 됩니다.

접근 방법

이 문제는 뒤에서 앞으로 진행하는 동적 계획법(DP)으로 깔끔하게 해결할 수 있습니다. 각 위치에서 마지막 칸(N번째 위치)까지 도달하는 데 드는 최소 비용을 미리 계산해 두면, 시작점에서부터 next 포인터를 따라가며 최종 경로를 복원할 수 있습니다.

해결 과정은 다음 단계를 따릅니다 −

  • n := 배열 A의 크기

  • 결과를 저장할 배열 ret을 정의합니다

  • 크기가 n인 배열 cost를 정의하고 모든 값을 무한대(inf)로 초기화합니다

  • 크기가 n인 배열 next를 정의하고 모든 값을 -1로 초기화합니다

  • n이 0이거나 A[n - 1]이 -1이면 −

    • 빈 배열을 반환합니다

  • endPoint := n - 1

  • cost[n - 1] = A[n - 1]

  • i := n - 2로 초기화한 뒤, i ≥ 0을 만족하는 동안 i를 1씩 감소시키며 반복 −

    • A[i]가 -1이면 −

      • 다음 반복으로 건너뜁니다

    • j를 i + 1부터 (n - 1)과 i + B 중 작은 값까지 1씩 증가시키며 반복 −

      • cost[j] + A[i] < cost[i]이면 −

        • cost[i] := cost[j] + A[i]

        • next[i] := j

        • endPoint := i

  • endPoint가 0이 아니면 −

    • 빈 배열을 반환합니다

  • endPoint가 -1이 아닌 동안 endPoint = next[endPoint]로 갱신하며 반복 −

    • ret의 끝에 endPoint + 1을 삽입합니다

  • ret을 반환합니다

핵심 아이디어는 다음과 같습니다. 뒤에서 앞으로 탐색하면서 cost[i]에는 'i에서 출발해 마지막 칸까지 가는 최소 비용'이 저장되고, next[i]에는 그 비용을 달성하는 다음 위치가 기록됩니다. 내부 반복문에서 j를 왼쪽(i+1)에서 오른쪽으로 순회하면서 엄격한 부등호(<)로 비교하기 때문에, 비용이 같은 후보가 여러 개일 때 항상 더 작은 인덱스가 선택됩니다. 이 덕분에 최종적으로 얻은 경로가 자연스럽게 사전순으로 가장 작은 경로가 됩니다.

모든 계산이 끝난 뒤 endPoint가 0이 아니라면 시작 위치에서 한 번도 갱신이 일어나지 않았다는 뜻이므로 유효한 경로가 존재하지 않습니다. 반대로 endPoint가 0이라면 next 포인터를 따라가며 실제 경로를 구성할 수 있습니다.

예제 살펴보기

A = [1, 2, 4, -1, 2], B = 2인 경우를 보겠습니다. A[4] = -1이므로 인덱스 4는 경로에 포함될 수 없습니다. 경로 [1, 3, 5]는 1 + 4 + 2 = 7의 비용이 들지만, 경로 [1, 2, 3, 5]는 1 + 2 + 4 + 2 = 9의 비용이 듭니다. 따라서 최소 비용 경로는 [1, 3, 5]입니다.

시간 복잡도는 O(N×B)이고, 공간 복잡도는 O(N)입니다.

예제 코드

더 잘 이해하기 위해 다음 구현을 살펴보겠습니다 −

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> cheapestJump(vector<int>& A, int B) {
      int n = A.size();
      vector <int> ret;
      vector <int> cost(n, 1e9);
      vector <int> next(n, -1);
      if(!n || A[n - 1] == -1) return {};
      int endPoint = n - 1;
      cost[n - 1] = A[n - 1];
      for(int i = n - 2; i >= 0; i--){
         if(A[i] == -1) continue;
         for(int j = i + 1 ; j <= min(n - 1, i + B); j++){
            if(cost[j] + A[i] < cost[i]){
               cost[i] = cost[j] + A[i];
               next[i] = j;
               endPoint = i;
            }
         }
      }
      if(endPoint != 0) return {};
      for(;endPoint != - 1; endPoint = next[endPoint]){
         ret.push_back(endPoint + 1);
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,4,-1,2};
   print_vector(ob.cheapestJump(v, 2));
}

입력

{1,2,4,-1,2}, 2

출력

[1, 3, 5]