23.03.28. 풀었던 문제들

Leetcode 983. Minimum Cost For Tickets

 dp로 풀리는 문제. dp[i]를 ith day의 cost라 하자. 그러면 다음과 같은 점화식을 찾을 수 있다.

• dp[i-1] + [현재 값이 day에 있으면 cost[0]]
• dp[i-7] + 7일권 cost
• dp[i-30] + 30일권 cost

 

 항상 그렇듯 dp[i]를 뭘로 정의하냐에 따라 점화식을 세우기 쉬워지기도 하고, 어려워지기도 한다. 점화식을 잘 세워보자.

// Runtime 4 ms Beats 69.83%
// Memory 9.6 MB Beats 81.2%

class Solution {
public:
    int handleOutbound(int day, int value){
        if(day - value < 0) return 0;
        return day - value;
    }
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int INF = days[days.size()-1] + 1;
        cout<<INF<<endl;
        vector<int> dp(INF, 0);
        for(int i = 1, didx = 0; i<INF; i++){
            dp[i] = dp[i-1];
            if(didx < days.size() && days[didx] == i){
                dp[i] += costs[0];
                didx++;
            }
            dp[i] = min(dp[i], dp[handleOutbound(i, 7)] + costs[1]);
            dp[i] = min(dp[i], dp[handleOutbound(i, 30)] + costs[2]);
        }
        
        return dp[INF-1];
    }
};

 

시간복잡도 & 공간복잡도

 처음부터 끝까지 탐색한다. 이 때 INF의 max값은 365이므로 O(365)