Minimum Cost For Tickets(leetcode, 983)

NJW·2023년 3월 28일

코테

목록 보기

145/170

문제 설명

기차 여행을 하는 날짜가 주어진다. 얼마나 이동할 수 있는지에 대한 기차표 가격이 주어졌을 때, 제일 적은 값으로 이동하는 값을 구하라.

위에는 어느정도 요약을 한 것이고 문제에서 주어진 Example 1을 가지고 조금 더 자세히 설명해보겠다.

Input: days = [1,4,6,7,8,20], costs = [2,7,15]

우리는 총 1일부터 20일까지 여행을 한다. 그런데 이때, days에 들어간 날들이 기차로 이동해야 하는 날짜이다. 즉, [1, 4, 6, 7, 8, 20]일에는 기차에 타 있어야 한다는 것이다.

이때 하루만 기차로 이동할 수 있는 패스는 costs[0]으로 가격은 2, 칠 일을 기차로 이동할 수 있는 패스는 costs[1]로 가격은 7, 삼십 일을 이동할 수 있는 패스는 costs[2]로 가격은 15 이렇게 된다.

그렇다면, 첫 번째 날짜에 day-1 pass를 사고, 세 번째 날짜에 day-7 pass를 사서 3부터 9일까지 사용할 수 있게 하고, 마지막 날인 20일에 day-1 pass를 사면 기차로 이동할 수 있는 최소 값은 11이다.

문제 풀이

첫 번째 접근

문제를 보자마자 생각했다. 완전 DP문제잖아! 그리고 각 날짜에 각 티켓을 살 경우 나오는 값의 최솟값을 구헤야 하나 생각했다. 근데 이렇게 하면 DP가 아니라 트리 문제가 되는데... 그리고 시간도 엄청 걸릴 거다.

아아~ 문제 유형은 알지만 도저히 풀이를 모르겠어서 다른 사람의 풀이를 봤다. DP는 꾸준히 풀어줘야 감을 잃지 않는 거 같다.

두 번째 접근

DP의 수식은 ~~언제나 그렇듯이~~ 생각보다 간단했다.
첫 번째 패스를 살 값과 두 번째 패스를 살 값과 세 번째 패스를 살 값을 비교해서 최솟 값을 넣어주면 된다.

일단 기차로 이동해야 하는 각 날짜를 set()에 넣어준다. 그리고 반복문을 1부터 365까지 돌려주는데, 만일 i가 기차로 이동해야 하는 날짜이면 해당 날짜에 살 티켓의 값을 구해준다.

문제 설명 예시에서는 세 번쨋 날 구매한다고 했지만, 기차로 이동하는 각 날짜에 구매해도 큰 문제는 없다.

첫 번째 패스를 살 경우는 오로지 하루만 이동하는 것이기 때문에 바로 직전의 값에다가 첫 번째 패스 값을 더해주면 된다.

두 번째 패스를 살 경우는 7일을 이동하는 것이기에 0혹은 현재 위치에서 7을 뺀 값의 최댓값에다가 두 번째 패스를 값을 더해주면 된다. 여기서 dp[max(0, i-7)0]을 해주는 경우는 만일 우리가 최대 6일을 이동한다고 가정하자. 그렇다면 매일마다 첫 번째 패스를 사는 것보다 두 번째 패스를 사는 것이 이득이다(하루가 남는다고 해도). 그러나 i가 6이기에 dp[]안에 들어가는 값이 음수가 된다. 이를 방지하기 위해 0과 i-7의 최댓값을 구해주는 것이다. 그렇게 되면 dp[0] + cost[1]이 되어 우리가 원하는 값이 나온다.

세 번째 패스 또한 두 번째 패스와 유사하다.

코드

Java

import java.util.*;

class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        Set<Integer> Set_days = new HashSet<>();
        int[] dp = new int[366];

        for(int day : days){
            Set_days.add(day);
        }

        for(int i=1; i<366; i++){
            if(Set_days.contains(i)){
                dp[i] = Math.min(Math.min(dp[i-1] + costs[0], dp[Math.max(0, i-7)] + costs[1]), dp[Math.max(0, i-30)] + costs[2]);
            }else{
                dp[i] = dp[i-1];
            }
        }

        return dp[365];
    }
}

Python

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        dp = [0] * 366
        Set_days = set(days)

        for i in range(1, 366):
            if i in Set_days:
                dp[i] = min(dp[i-1] + costs[0] , dp[max(0, i-7)] + costs[1], dp[max(0, i-30)] + costs[2])
            else:
                dp[i] = dp[i-1]
        
        return dp[365]