983. Minimum Cost For Tickets

문제

https://leetcode.com/problems/minimum-cost-for-tickets/description/?envType=problem-list-v2&envId=dynamic-programming

풀이

class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        int[] dp = new int[days[days.length-1] + 1];
        boolean[] travel = new boolean[days[days.length-1] + 1];

        for(int i = 0; i < days.length; i++) {
            travel[days[i]] = true;
        }


        // 여행을 가는 날이 아니면 티켓이 필요가 없다
        // -> 전 날 비용을 그대로 사용    
        for(int i = 1; i <= days[days.length-1]; i++) {
            if(travel[i] == false) {
                dp[i] = dp[i-1];
                continue;
            }

            dp[i] = costs[0] + dp[i-1]; // 1일권을 산 경우
            dp[i] = Math.min(dp[i], costs[1] + dp[Math.max(i - 7, 0)]); // 7일 권을 산 경우 
            // i-7 까지의 최소 비용이 구해져 있을 거고, 거기에 costs[1]
            dp[i] = Math.min(dp[i], costs[2] + dp[Math.max(i - 30, 0)]); // 30일권을 산 경우
        }

        return dp[days[days.length-1]];
        
    }
}