Leetcode 983. Minimum Cost For Tickets with Python

문제

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.

당신은 1년 전부터 미리 여행 계획을 전부 세워놨습니다.
days 배열은 당신이 여행갈 날짜를 담고 있습니다.
costs 배열은 3개의 원소로 이루어져 있으며, 각각 1일권, 7일권, 30일권의 가격입니다.
여행을 가장 값 싸게 갈수 있는 비용을 구하시오.

예시

Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation : 1일권 + 7일권 + 1일권

Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
Output: 17
Explanation : 30일권 + 1일권

풀이법

DP를 이용하여 풀었다.
총 366개의 모든 날짜가 담긴 배열을 만들어
1~i일까지 여행했을때 최소비용을 담도록 했다.

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        calendar = [0 for _ in range(366)]
        index = 0
        
        for (i, v) in enumerate(calendar):
            if i == 0: continue
                
            if i > days[len(days)-1] + 30:
                break
            
            if index < len(days):
                if i != days[index] and i < 7:
                    calendar[i] = calendar[i-1]
                elif i != days[index] and i < 30:
                    calendar[i] = min(calendar[i-1], min(calendar[i-7:i]) + costs[1])
                elif i != days[index]:
                    calendar[i] = min(calendar[i-1], min(calendar[i-7:i]) + costs[1], min(calendar[i-30:i-7]) + costs[2])
                elif i < 7:
                    calendar[i] = calendar[i-1] + costs[0]
                    index += 1
                elif i < 30:
                    calendar[i] = min(min(calendar[i-7:i]) + costs[1], calendar[i-1] + costs[0])
                    index += 1
                else:
                    calendar[i] = min(min(calendar[i-30:i-7]) + costs[2],min(calendar[i-7:i]) + costs[1], calendar[i-1] + costs[0])
                    index += 1
            else:
                if i < 7:
                    calendar[i] = calendar[i-1]
                elif i < 30:
                    calendar[i] = min(calendar[i-1], min(calendar[i-7:i]) + costs[1])
                else:
                    calendar[i] = min(calendar[i-1], min(calendar[i-30:i-7]) + costs[2], min(calendar[i-7:i]) + costs[1])
            
        lastDay = days[len(days)-1]
        
        return calendar[days[len(days)-1]]