[Leetcode]983.Minimum Cost For Tickets

풀이

days와 일자별 pass 가격이 배열로 주어진다.

이때 주어진 days를 모두 여행할 수 있는 최소 pass 가격을 구하면 되는 문제다.

DP 방식으로 풀이했다.(사실 DP인걸 알고 시작했다..)

1.days에 있는 가장 큰 수 크기 +1 만큼의 배열을 생성한다.
2.배열을 돌면서 days 배열에 있는 날짜의 값에 적절한 pass 가격을 넣어주고, 없는 날짜라면 이전 날짜의 값을 저장한 후 넘어간다.

pass의 가격은 해당 day에서 각각 1,7,30일 전에 가장 쓴 돈이 적은 값을 사용하고, 그 값으로 배열을 업데이트 한다.

코드

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        max_day = days[-1]
        dp = [0] * (max_day + 1)
        check_day = set(days)

        for i in range(1,max_day + 1):
            if i in check_day:
                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[max_day]