[LeetCode] 983. Minimum Cost For Tickets

https://leetcode.com/problems/minimum-cost-for-tickets/description/

leetcode - Minimum Cost For Tickets

문제 유형: 다이나믹 프로그래밍

문제 난이도: Medium

 

문제

You have planned some train traveling one year in advance. The days of the year in which you will travel are given as an integer array days. Each day is an integer from 1 to 365.

Train tickets are sold in three different ways:

• a 1-day pass is sold for costs[0] dollars,
• a 7-day pass is sold for costs[1] dollars, and
• a 30-day pass is sold for costs[2] dollars.

The passes allow that many days of consecutive travel.

• For example, if we get a 7-day pass on day 2, then we can travel for 7 days: 2, 3, 4, 5, 6, 7, and 8.

Return the minimum number of dollars you need to travel every day in the given list of days.

 

days의 날짜에는 기차여행을 잔다.

days에는 1에서 365의 범위의 수들이 오름차순으로 정렬되어있다.

costs[0]에는 일일권,

costs[1]에는 7일권,

costs[2]에는 30일권 가격이 있다.

가장 저렴하게 1년 동안 여행을 다니는 기차가격을 구하시오.

 

풀이

dp[i] = i번째 날까지의 최소비용이다.

0번째날은 비용이 0이다.

만약에 i번째날이 여행일이 아니라면, 티케팅할 이유가 없다. dp[i] = dp[i-1]이다.

만약에 여행일이라면, 당일만 하는 방법, 7일전에 7일패스를 끊는방법, 30일전에 30일패스를 끊는방법 중 세 가지 중 가장 싼 방법을 이용해야 한다.

 

최종적으로 dp[마지막날짜]가 답이다.

 

코드

C++

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        unordered_set<int> travel(days.begin(), days.end());
        int n = days.size();
        int lastday = days.back();
        vector<int> dp(lastday + 1, 0);
        for(int i = 1; i <= lastday; ++i) {
            if(travel.find(i) == travel.end()) {
                dp[i] = dp[i-1];
            } else {
                dp[i] = min({
                    dp[i-1] + costs[0],
                    dp[max(0, i-7)] + costs[1],
                    dp[max(0, i-30)] + costs[2],
                });
            }
        }

        return dp[lastday];
    }
};