C++의 티켓에 대한 최소 비용

<시간/>

기차 여행으로 인기 있는 국가가 있다고 가정해 보겠습니다. 우리는 1년 전에 기차 여행을 계획했습니다. 우리는 여행할 날짜를 담고 있는 배열을 가지고 있습니다. 매일은 1에서 365 사이의 정수입니다. 기차표는 세 가지 다른 방식으로 판매됩니다 -

1일 이용권은 비용[0]달러에 판매됩니다.
1일 이용권은 비용[0]달러에 판매됩니다.
30일권을 [2]달러에 판매합니다.

여기에서 패스를 사용하면 여러 날의 연속 여행이 가능합니다. 예를 들어, 2일차에 7일권 1장을 받으면 7일 동안 여행할 수 있습니다(2일, 3일, 4일, 5일, 6일, 7일, 8일 연속). 주어진 날짜 목록에서 매일 여행하는 데 필요한 최소 금액을 찾아야 합니다. 따라서 입력이 [1,4,6,7,8,20]이고 비용이 [2,7,15]인 경우 출력은 11이 됩니다.

1일차에 비용[0] =$2, 즉 1일차를 포함하는 1일권을 구입했고, 3일차에 7일권을 구입했으므로 비용[1] =$7, 즉 3일부터 9일까지 , 그리고 20일차에 다시 1일권을 구입했으므로 비용[0] =$2, 즉 20일차를 포함합니다. 따라서 총 $11가 지출됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

크기가 366인 dp라는 배열 하나를 만듭니다.
j :=0
1에서 366 사이의 i에 대해
- dp[i] :=비용[0] + dp[i - 1]
- i – 7>=0이면 dp[i] :=dp[i - 7] + 비용[1] 및 dp[i]
  의 최소값
- i – 30>=0이면 dp[i] :=dp[i - 30] + 비용[2] 및 dp[i]
  의 최소값
- j <일 배열의 크기이고 days[j] =i이면 j를 1만큼 증가시키고, 그렇지 않으면 dp[i] :=dp[i]의 최소값, dp[i – 1]
반환 dp[365]

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int mincostTickets(vector<int>& days, vector<int>& costs) {
      vector <int> dp(366);
      int j = 0;
      for(int i = 1; i < 366; i++){
         dp[i] = costs[0] + dp[i - 1];
         if(i - 7 >= 0){
            dp[i] = min(dp[i - 7] + costs[1], dp[i]);
         }
         if(i - 30 >= 0){
            dp[i] = min(dp[i - 30] + costs[2], dp[i]);
         }
         if(j < days.size() && days[j] == i){
            j++;
         }else
            dp[i] = min(dp[i], dp[i - 1]);
      }
      return dp[365];
   }
};
main(){
   vector<int> v = {1,4,6,7,8,20};
   vector<int> v1 = {2,7,15};
   Solution ob;
   cout << (ob.mincostTickets(v, v1));
}

입력

[1,4,6,7,8,20]
[2,7,15]