LeetCode 983. Minimum Cost For Tickets (JAVA)

출처 : 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, anda 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.


당신은 1년 후의 기차 여행을 계획하고 있습니다. 여행을 갈 날짜들이 정수 배열 days로 주어집니다. 각 날짜는 1부터 365까지의 정수입니다.
기차 티켓은 세 가지 방법으로 판매됩니다:
1일 이용권은 costs[0] 달러에 판매됩니다.
7일 이용권은 costs[1] 달러에 판매됩니다.
30일 이용권은 costs[2] 달러에 판매됩니다.
이 이용권들은 해당 일수만큼 연속적으로 여행할 수 있도록 해줍니다.
예를 들어, 2일에 7일 이용권을 구매하면 2, 3, 4, 5, 6, 7, 8일 동안 여행할 수 있습니다.주어진 days 리스트에 있는 모든 날짜에 여행하려면 필요한 최소 비용을 반환하세요.

 

접근 : DP

 

1~days[days.length-1] 일 까지 1일, 7일, 30일 이용권을 구매했을때의 최솟값을 구한다.

 

현재 i일 일때

1일 이용권 금액 : dp[i-1] + costs[0]

7일 이용권 금액 : dp[i-7] + costs[1]

30일 이용권 금액 : dp[i-30] + costs[2]

 

주의

days = [1,4] 라면

1일 이용권 금액 기준 : dp[4] = dp[3] + costs[0] = dp[1] + costs[0] 이여야함

즉, days 에 포함되지 않은 날의경우 cost를 더하면 안됨

days의 날짜 포함여부를 판단하기위해 Set자료구조 사용

 

Set 사용

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        int n = days.length;
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            set.add(days[i]);
        }
        int[] dp = new int[days[n-1]+1];

        for (int i = 1; i < dp.length; i++) {
            if(!set.contains(i)){
                dp[i] = dp[i-1];
                continue;
            }
            int cost1 = dp[i-1] + costs[0];
            int cost7 = costs[1];
            int cost30 = costs[2];
            if(i-7>=0){
                cost7 = dp[i-7] + costs[1];
            }
            if(i-30>=0){
                cost30 = dp[i-30] + costs[2];
            }
            dp[i] = Math.min(cost1, Math.min(cost7, cost30));
        }

        return dp[days[n-1]];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.mincostTickets(new int[]{1},new int[]{3,2,1});
    }
}

 

 

Set사용 X

public class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        int n = days.length;
        int[] dp = new int[days[n-1]+1];
        int index = 0;
        for (int i = 1; i < dp.length; i++) {
            if(i != days[index]){
               dp[i] = dp[i-1];
            }else{
                index++;
                int cost1 = dp[i-1] + costs[0];
                int cost7 = costs[1];
                int cost30 = costs[2];
                if(i-7>=0){
                    cost7 = dp[i-7] + costs[1];
                }
                if(i-30>=0){
                    cost30 = dp[i-30] + costs[2];
                }
                dp[i] = Math.min(cost1, Math.min(cost7, cost30));
            }


        }

        return dp[days[n-1]];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.mincostTickets(new int[]{1},new int[]{3,2,1});
    }
}