Minimum Cost For Tickets(Array,Dynamic Programming)

https://leetcode.com/problems/minimum-cost-for-tickets/description/?envType=daily-question&envId=2024-12-31

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.

 

Example 1:

Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total, you spent $11 and covered all the days of your travel.

Example 2:

Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
Output: 17
Explanation: For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 30-day pass for costs[2] = $15 which covered days 1, 2, ..., 30.
On day 31, you bought a 1-day pass for costs[0] = $2 which covered day 31.
In total, you spent $17 and covered all the days of your travel.

 

Constraints:

• 1 <= days.length <= 365
• 1 <= days[i] <= 365
• days is in strictly increasing order.
• costs.length == 3
• 1 <= costs[i] <= 1000

요즘 계속 DP 문제가 제시된다.

 

함 봐보자.

 

DP도 풀다보면 는다던데 과연...!

 

역시나 문제는 완벽하게 이해가 가는데,,, 이걸 또 우찌 구현해야하 할까.. 라는 생각이 든다.

 

일단 Greedy하게 함 봐보기

 

1. Python

 

앵간히 했는데.. 자꾸 삑사리가 난다 ㅠㅠ

아오 속상해

 

실패한 내 코드는 아래와 같다.. 기본 test는 뚫는데 edge case 처리가 부족하다..

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        # make DP list and calculate Minimum cost until each day in 'days'
        # initialize
        dp = [0]*len(days)
        dp[0] = min(costs)
        idx1 = 0 # week based index
        idx2 = 0 # month based index
        for i in range(1,len(days)):
            daily = dp[i-1]+costs[0]
            # weekly
            while days[i] >= days[idx1]+7 and idx1 < i-1:
                idx1 += 1
            weekly = costs[1] if idx1==0 else dp[idx1] + costs[1]
            # monthly
            while days[i] >= days[idx2]+30 and idx2 < i-1:
                idx2 += 1
            # print('idx2: ',idx2)
            monthly = costs[2] if idx2==0 else dp[idx2] + costs[2]
            dp[i] = min(daily,weekly,monthly)
        return dp[-1]

 

 

ㅠㅠ 나름 고민 많이 했는데 뭐가 문제냐!!

 

근데 이상한게 GPT에 수정을 맡겨서 아래처럼 코드가 나왔는데 이건 또 잘 작동한다..

 

# 모범답안
class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        # Initialize DP array
        dp = [0] * len(days)
        dp[0] = min(costs)
        
        idx1, idx2 = 0, 0  # Pointers for 7-day and 30-day passes
        
        for i in range(1, len(days)):
            # Calculate daily cost
            daily = dp[i - 1] + costs[0]
            
            # Move idx1 to find the starting point for a 7-day pass
            while days[i] >= days[idx1] + 7:
                idx1 += 1
            weekly = costs[1] if idx1 == 0 else dp[idx1 - 1] + costs[1]
            
            # Move idx2 to find the starting point for a 30-day pass
            while days[i] >= days[idx2] + 30:
                idx2 += 1
            monthly = costs[2] if idx2 == 0 else dp[idx2 - 1] + costs[2]
            
            # Update dp for the current day
            dp[i] = min(daily, weekly, monthly)
        
        return dp[-1]

 

아... indexing의 차이였다.. 아이디어는 맞았으나 제기랄.. 이럴 때가 참 허무하다

 

Array index 잘 확인하기 ㅠㅠ

 

어쨌든 졌잘싸다.. 하 좀만 더 집중하기..!

 

 

2.C++

좀 추잡하게 min 값을 정해준거 말곤 Python 코드와 동일하다

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int n = days.size();
        vector<int> dp(n,0);
        int ans,day,week,month;
        ans = min(costs[0],costs[1]);
        ans = min(ans,costs[2]);
        dp[0] = ans;
        int idx1 , idx2 = 0;
        for(int i=1;i<n;i++){
            day = dp[i-1]+costs[0];

            while( days[i] >= days[idx1]+7 ) idx1 ++;
            week = idx1==0 ? costs[1] : dp[idx1-1]+costs[1];

            while( days[i] >= days[idx2]+30 ) idx2 ++;
            month = idx2==0 ? costs[2] : dp[idx2-1]+costs[2];
            ans = min(day,week);
            ans = min(ans,month);
            dp[i] = ans;
        }
        return dp[n-1];
    }
};

 

 

3. C

참고사항

#C
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int mincostTickets(int* days, int daysSize, int* costs, int costsSize) {
    int last_day = days[daysSize - 1];
    int dp[last_day + 1];
    bool isTravelDay[last_day + 1];

    // Initialize DP and travel days
    for (int i = 0; i <= last_day; i++) {
        dp[i] = 0;
        isTravelDay[i] = false;
    }
    for (int i = 0; i < daysSize; i++) {
        isTravelDay[days[i]] = true;
    }

    // DP computation
    for (int i = 1; i <= last_day; i++) {
        if (!isTravelDay[i]) {
            dp[i] = dp[i - 1];
        } else {
            int cost1 = dp[i - 1] + costs[0];
            int cost7 = dp[i >= 7 ? i - 7 : 0] + costs[1];
            int cost30 = dp[i >= 30 ? i - 30 : 0] + costs[2];
            dp[i] = cost1 < cost7 ? (cost1 < cost30 ? cost1 : cost30) : (cost7 < cost30 ? cost7 : cost30);
        }
    }

    return dp[last_day];
}

int main() {
    int days[] = {1, 4, 6, 7, 8, 20};
    int costs[] = {2, 7, 15};
    int daysSize = sizeof(days) / sizeof(days[0]);
    int costsSize = sizeof(costs) / sizeof(costs[0]);

    int result = mincostTickets(days, daysSize, costs, costsSize);
    printf("Minimum cost: %d\n", result);
    return 0;
}