983. Minimum Cost For Tickets - DP

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

Minimum Cost For Tickets - LeetCode

 주어진 days에 train 여행을 할 수 있는 티켓을 사는 경우 중 가장 작은 가격의 합을 구하는 문제다.  중요 포인트는 1일, 7일, 30일에 대한 티켓이 있고 이를 days에 있는 날들을 사용해서 푸는 것이다.  흠...

 

class Solution {
public:
    int cache[366];
    unordered_set<int> dayset;
    
    int dp(vector<int>& days, vector<int>& costs, int cur){
        if(cur > 365) return 0;
        
        int &ret = cache[cur];
        if(ret != -1) return ret;
        ret = INT_MAX;
        
        if(dayset.find(cur) != dayset.end()){
            ret = min(dp(days, costs, cur + 1) + costs[0], 
                      min(dp(days, costs, cur + 7) + costs[1], 
                          dp(days, costs, cur + 30) + costs[2]));
        } else {
            ret = dp(days, costs, cur + 1);
        }
        return ret;
    }
    
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        for(auto day : days){
            dayset.insert(day);
        }
        memset(cache, -1, sizeof(cache));
        return dp(days, costs, 0);
    }
};

 365만큼 돈다.  days에 있는 day면 1, 7, 30을 더해서 dp를 call하고 cost를 각각 반환값과 더해서 가장 작은 값을 캐시에 넣는다.  days에 들어가지 않는 day인 경우 days에 있는 day가 나올 때까지 1씩 더해서 dp를 call해준다.  이 의미는 days에 있는 day만 cost를 가져가겠다는 뜻으로 days에 들어가지 않은 day는 무시하겠다는 뜻이다.  정확하게는 days의 각각의 day 사이에 있는 값들 중 costs의 범위에 걸리지 않는 값들을 무시한다.

 

Time complexity: O(N), N: 365

Space complexity: O(N)

 

class Solution {
public:
    int cache[366];
    vector<int> durations = {1, 7, 30};
    
    int dp(vector<int>& days, vector<int>& costs, int cur){
        int n = days.size();
        
        if(cur >= n){
            return 0;
        }
        
        int &ret = cache[cur];
        if(ret != -1){
            return ret;
        }
        ret = INT_MAX;
        int j = cur;
        for(int i = 0; i < 3; i++){
            while(j < n && days[j] < days[cur] + durations[i]){
                j++;
            }
            ret = min(ret, dp(days, costs, j) + costs[i]);
        }
        return ret;
    }
    
    
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        memset(cache, -1, sizeof(cache));
        return dp(days, costs, 0);
    }
};

 days에 있는 값들을 이용해서 현재 위치에서 duration(1 or 7 or 30)을 더한 값보다 큰 day를 찾는다.  문제의 요구사항 상 찾은 day부터 1 or 7 or 30 day의 티켓을 사야하므로 해당 day부터 call하면 된다.  답은 call한 return 값과 cost를 더해준다.

 

Time complexity: O(M), M == days.size()

Space complexity: O(N)