[LeetCode] 983. Minimum Cost For Tickets - Java/Dart

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

Minimum Cost For Tickets - LeetCode

---

문제

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

---

풀이

풀이 과정

여행일이 담긴 배열 days 와 1-day pass, 7-day pass, 30-day pass의 가격이 담긴 costs 배열이 주어질 때 days 배열의 날짜를 모두 여행하기 위해 구매해야하는 pass의 최소 가격을 구하는 문제이다.

dp를 이용하여 1일 부터 마지막 날짜까지 각 날짜에 들어가는 최소 비용을 구해나가도록 풀이한다.

먼저 각 여행일의 최소 비용을 저장할 배열을 선언하고 days 배열의 마지막 날짜까지 탐색할 수 있도록 크기를 초기화한다.

// 각 여행일의 최소 비용을 저장할 배열을 선언하고
// days 배열의 마지막 날짜 + 1 크기로 초기화한다
int[] costSum = new int[days[days.length - 1] + 1];

 

실제 여행일에 해당하지 않는 날의 경우에는 비용이 발생하지 않으므로 전날까지의 비용을 그대로 가지고 있으면 된다.
실제 여행일을 판단하기 위해서 마찬가지로 days 배열의 마지막 날짜 + 1 크기의 boolean 배열을 선언하고 days 배열의 값에 해당하는 날짜들을 true로 세팅해준다.

// 실제 여행일에 해당하는 날짜를 저장하기위한 배열 선언 및
// days 배열에 해당하는 날짜 true로 세팅
boolean[] travelDay = new boolean[days[days.length - 1] + 1];

for(int day : days) {
    travelDay[day] = true;
}

 

1일부터 여행의 마지막 날까지 탐색하며 각 날짜에 필요한 최소 비용을 업데이트 한다.
현재 탐색중인 날짜가 실제 여행한 날짜에 포함되지 않는 경우는 이전 날짜의 비용을 유지하고 다음 탐색으로 넘어간다.
현재 탐색중인 날짜가 실제 여행한 날짜인 경우 다음 세 가지의 값 중 최소값으로 값을 업데이트한다.

• 1일 전과 1-day pass 비용의 합
• 7일 전과 7-day pass 비용의 합
• 30일 전과 30-day pass 비용의 합

for(int i = 1; i < costSum.length; i++) {
// 여행한 날짜에 포함되지 않는 경우
if(!travelDay[i]) {
    // 전일 비용을 유지하고 탐색을 계속
    costSum[i] = costSum[i - 1];
    continue;
}

// 1일 전과 1-day 패스 비용의 합
// 7일 전과 7-day 패스 비용의 합
// 30일 전과 30-day 패스 비용의 합 중 가장 작은 값을 현재 비용으로 저장 
costSum[i] = costSum[i - 1] + costs[0];
costSum[i] = Math.min(costSum[i], costSum[Math.max(0, i - 7)] + costs[1]);
costSum[i] = Math.min(costSum[i], costSum[Math.max(0, i - 30)] + costs[2]);
}

 

탐색이 종료된 후 여행의 마지막 날짜에 해당하는 값을 return 한다.

// 마지막 일자의 비용을 return
return costSum[costSum.length - 1];

---

최종 코드

• Java

class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        // 각 여행일의 최소 비용을 저장할 배열을 선언하고
        // days 배열의 마지막 날짜 + 1 크기로 초기화한다
        int[] costSum = new int[days[days.length - 1] + 1];
        // 실제 여행일에 해당하는 날짜를 저장하기위한 배열 선언 및
        // days 배열에 해당하는 날짜 true로 세팅
        boolean[] travelDay = new boolean[days[days.length - 1] + 1];
        
        for(int day : days) {
            travelDay[day] = true;
        }
        
        for(int i = 1; i < costSum.length; i++) {
            // 여행한 날짜에 포함되지 않는 경우
            if(!travelDay[i]) {
                // 전일 비용을 유지하고 탐색을 계속
                costSum[i] = costSum[i - 1];
                continue;
            }
            
            // 1일 전과 1-day 패스 비용의 합
            // 7일 전과 7-day 패스 비용의 합
            // 30일 전과 30-day 패스 비용의 합 중 가장 작은 값을 현재 비용으로 저장 
            costSum[i] = costSum[i - 1] + costs[0];
            costSum[i] = Math.min(costSum[i], costSum[Math.max(0, i - 7)] + costs[1]);
            costSum[i] = Math.min(costSum[i], costSum[Math.max(0, i - 30)] + costs[2]);
        }
        
        // 마지막 일자의 비용을 return
        return costSum[costSum.length - 1];
    }
}

• Dart

class Solution {
  int mincostTickets(List<int> days, List<int> costs) {
    // 각 여행일의 최소 비용을 저장할 리스트를 선언하고
    // days 배열의 마지막 날짜 + 1 크기로 초기화한다
    List<int> costSum = List<int>.filled(days[days.length - 1] + 1, 0);
    // 실제 여행일에 해당하는 날짜를 저장하기위한 배열 선언 및
    // days 배열에 해당하는 날짜 true로 세팅
    List<bool> travelDay = List<bool>.filled(days[days.length - 1] + 1, false);
    
    for(var day in days){
        travelDay[day] = true;
    }
    
    for(var i = 1; i < costSum.length; i++){
        // 여행한 날짜에 포함되지 않는 경우
        if(!travelDay[i]){
        // 전일 비용을 유지하고 탐색을 계속
        costSum[i] = costSum[i - 1];
        continue;
        }
        
        // 1일 전과 1-day 패스 비용의 합
        // 7일 전과 7-day 패스 비용의 합
        // 30일 전과 30-day 패스 비용의 합 중 가장 작은 값을 현재 비용으로 저장 
        costSum[i] = costSum[i - 1] + costs[0];
        costSum[i] = min(costSum[i], costSum[max(0, i - 7)] + costs[1]);
        costSum[i] = min(costSum[i], costSum[max(0, i - 30)] + costs[2]);
    }
    
    // 마지막 일자의 비용을 return
    return costSum[costSum.length - 1];
  }
}

---