983. Minimum Cost For Tickets

 

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

 

Difficulty : Medium

 

Status : Solved

 

Time : 00:17:48

 

---

 

문제 설명

 

 

당신은 미리 일 년치 기차 여행을 계획하고 있습니다. 당신이 일 년간 기차를 탈 일자들이 정수 배열 'days'로 주어집니다. 각각의 day는 1 ~ 365사이의 정수입니다.

기차표는 세 가지 다른 방법으로 판매됩니다.

 

• costs[0] 달러에 파는 1일 이용권
• costs[1] 달러에 파는 7일 이용권
• costs[2] 달러에 파는 30일 이용권

 

이 이용권들은 연속되는 수 일간의 여행동안 허용됩니다.

 

• 예를 들어, 우리가 2일차에 7일 이용권을 샀다면, 우리는 2, 3, 4, 5, 6, 7, 8 총 7일간 여행 가능합니다.

 

주어진 days 리스트에서 모든 일자를 여행하기 위해 필요한 최소 달러를 반환하세요.

 

---

 

풀이

 

dp로 풀어보자.

days[n] 일자를 우리는 반드시 여행해야 하며, 그 days[n]번째 일자 직전까지 소비한 최소 소비 금액을 dp[n]이라고 두자. 우리가 그 days[n]을 여행하기 위해서는 1일권, 7일권, 30일권을 살 수 있다.

 

그럼 각각의 이용권(기간 m)에 대해 최대한 여행할 수 있는 기간은 [days[n], days[n]+m-1]이다(기왕이면 하나의 이용권으로 한 번에 여행가는 게 효율적임을 우리는 잘 알고 있다) 그렇다면 n번째 뒤의 days[n]+m-1 이후의 일자에는 우리는 새로 이용권을 구매해야만 한다. 이 때의 인덱스를 i라 두면...

dp[i] = min(dp[i], dp[n] + cost)

days[i] > days[n] + m - 1

식이 성립하게 된다.

총 시간복잡도는 O(len(days)^2)가 된다. 조건을 만족하는 일자를 반복적으로 찾아야 하기 때문.

 

풀이 코드

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        length = len(days)
        dp = [float('inf')]*(length+1)
        days.append(float('inf'))
        dp[0] = 0
        pass_days = [1, 7, 30]

        for i in range(length):
            for j in range(3):
                for k in range(i+1, length+1):
                    if days[k] >= days[i] + pass_days[j] :
                        dp[k] = min(dp[k], dp[i] + costs[j])
                        break

        return dp[-1]