Daily LeetCode Challenge - 983. Minimum Cost For Tickets

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

오늘 문제는 기차를 타는날 days 배열이 주어지고 1일권 7일권 30일권의 가격이 들어있는 cost 배열이 주어졌을때, 기차 여행을 할 수 있는 가장 적은 돈을 구하는 문제였다.

이 문제는 DP 를 이용해서 풀 수 있었는데,
먼저 작은 부분으로 나누어보자면 하루 여행하는데 드는 가격은 그 전날의 여행비용 + 오늘의 여행비용이 된다.

만약 days 배열안에 없다면 그냥 그 전날의 여행비용을 가져오면 되지만, days 배열 안에 있다면, 그날 1일권을 사는게 싼지, 7일권을 사는게 싼지, 30일권을 사는게 싼지 비교를 하여야한다.

1일권을 샀을때, 7일권을 샀을때, 30일권을 샀을때의 가격을 각각 비교해서 제일 낮은 가격을 당일의 여행비용으로 설정하고 365일의 마지막까지 반복하면 가장 낮은 여행비용을 구할 수 있다.

class Solution {
    fun mincostTickets(days: IntArray, costs: IntArray): Int {
        
        val daySet = days.toHashSet()
        
        val memo = Array(366) { 0 }
        
        for(i in 1..365) {
            if(daySet.contains(i)) {
                memo[i] = minOf(
                    (memo[i-1] + costs[0]),
                    (memo[Math.max(0, i-7)] + costs[1]),
                    (memo[Math.max(0, i-30)] + costs[2])
                )
            }else {
                memo[i] = memo[i-1]
            }
        }
        return memo[365]
    }
}