뒤죽박죽 코딩 이야기

2023년 03월 28일 화요일 - 흠 아직도 화욜?

오늘 올려볼 문제는 983번 Minimum Cost For Tickets 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

아니 문제 개어려워!!

입력

사진에서도 볼 수 있듯이 int 배열 2개가 입력으로 들어온다.

풀이 및 코드

여행을 하려는 날짜와 1일, 7일, 30일 짜리 pass 권에 대한 가격이 주어진다.

이 때 모든 날을 여행할 수 있는 가장 적은 돈을 구하는 문제이다.

오늘은 정말 많이 헤매고 정답을 찾았다.

dp를 사용했고 set을 사용했다. (set은 사용안할 수도 있긴하다..)

1. dp 길이를 days에서 가장 큰 날짜 + 1로 정해주고 큰값으로 채워넣는다
2. 이 후 dp 배열을 돌면서 이전 1, 7, 30일 날짜 전에 쓴 돈 중에 어떤것이 제일 작은지 판단하여 dp 배열을 업데이트 한다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        var set = new HashSet<Integer>();
        for(var day: days) set.add(day);
        
        var ranges = new int[] {1, 7, 30};
        
        int n = days.length;
        var dp = new int[days[n - 1] + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        
        int pre = 0;
        
        for(int day = 0; day < dp.length; day++) {
            if(!set.contains(day)) {
                dp[day] = dp[pre];
                continue;
            }
            
            for(int j = 0; j < 3; j++) {
                int beforeDay = Math.max(day - ranges[j], 0), cost = costs[j];
                
                pre = day;
                
                dp[day] = Math.min(dp[beforeDay] + cost, dp[day]);
            }
        }
        
        return dp[days[n - 1]];
    }
}

제출 화면

days에 날짜가 떨어져있는 바람에 너무 헤맸다..

또한 O(n)으로도 풀 수 있는 문제라서.. 아직 dp는 많이 부족한 걸 느낀 하루였다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.