[Leetcode]983. Minimum Cost For Tickets

문제 요약

• 알고리즘 분류: 동적계획법(DP)
• 난이도: Medium
• 문제내용:
  • 1 ~ 365여행가는 날들 days 변수와 1, 7, 30일 기준 이용료 costs를 준다.
  • days 날짜대로 여행 간다고 했을때 최소 비용 구하여라
• 사이트 주소: https://leetcode.com/problems/minimum-cost-for-tickets/description/

문제풀이

 이번 문제는 동적계획법(DP)으로 풀어야 통과되는 문제이다.  DP에 관한 성명은 아래 글에서 확인 해보면된다.

https://jih3508.tistory.com/89

[알고리즘 이론] 동적계획법(Dynamic Programming, DP)

 

문제 접근방법

 dp는 구현보다 아이디어를 요구하는 문제로서 생각만 한다면 코드 구현은 간단한다. 이번 문제는 일 기준으로 1-day, 7-day, 30-day 비용으로 최소 비용으로 구하면 되는 문제이다. 하지면 여행 일수가 기간이 아니라 각 일로 되어 있기 하나부터 열까지 체크 하기가 힘들다 그래서 1일 부터 days의 최대일까지 하나씩 구할 예정이다. 그러면 1,7,30일 기준으로 크기를 비교하면서 하면 풀면 된다. 일단 0일 부터 시작해서 maxDay까지 표기를 하고 0일은 cost 0으로 시작해서 1부터 탐색하면된다. days에 없는 것은 이전 날을 그대로 기입하고 있는 것은 전날 + 1-day, 7일 전 + 7-day, 30일전 + 30-day중 가장 작은 값을 구하면 된다. 그래서 점화식은 아래와 같다.

• days에 없는 경우: 전날을 기입한다.
• days에 있는 경우:
  • -1 day cost + 1-cost
  • -7 day cost + 7-cost(7일 전날 -일 경우 0에서 현재 일까지본다.)
  • -30 day cost+ 30-cost (30일 전날 -일 경우 0에서 현재 일까지본다.)

 점화식은 이렇게 보면 되고 이해가 되기 쉽도록 아래 예제를 보면 이해가 되기 쉬울것이다.

예제 

• days: [1,4,6,7,8,20]
• costs: [2,7,15]

 노란색은 days 일수를 표시한것이고 연두색은 값의 처리하는 것이라고 보면된다. 화살표는 어떤것이 최적의 비용을 표기하기위해 기간이라고 보면 될것이다. 그리고 0일 부터 시작해서 비용 0으로 표기하고 시작하면된다. 

• 1일: days에 포함이 되어 있다. 1일은 시작 지점이라서 0일 + costs 비용을 추가하면된다.
• 2일 ~ 3일: days에 포함은 되어 있지 않지만 각 일 수 계산하기 편하기 위해서 이전비용을 옮긴다고 보면된다.
• 4일: 3일 + 1-day cost와 0~4일 7-day cost와 비교 해서 작은 값을 기입하면 된다. 2+2 와 7중에 3일 + 1-day cost가 더 적기 때문에 3일 + 1-day cost값을 기입한다.
• 5일: days에 포함되어 있지 않기 때문에 4일 비용을 기입한다.
• 6일: 5일 + 1-day cost와 0~6일 7-day cost와 비교 해서 더 작은 값을 기입한다. 그럼 7-day cost가 더 적어서 7-day cost를 기입한다.
• 7일: 6일이랑 동일하다
• 8일: 7일 + 1-day cost와 0일 + 1~7일 7-day cost와 비교 해서 더 작은 값을 기입한다. 그럼 7-day cost가 더 적어서 7-day cost를 기입한다.
• 9~19일: days에 없어서 8일것을 기입한다.
• 20일: 아래 3개 점화식중 가장 적은 값을 기입하면된다. 그럼 19 + 1-day가 가장 적다.
  • 19 + 1-day
  • 13 + 7-day
  • 0~20 → 30-day

이렇게 구현하면 시간 복잡도는 O(N)만큼 나올것이다. 구현은 아래 코드를 보면 될것이다.

Code

Python

 List와 다르게 Set 자료구조로 포함되어있는지 확인하는 것은 O(1)만큼 나온다.

 

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

        for i in range(1, maxDays+1):

            if(i in checkDays):
                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[maxDays]

Java

 파이썬과 다르게 코드보면 days가 확인 하기 위해서 set자료구조를 사용하지 않기 때문에 시간복잡도는 O(N^2)만큼 나온다.

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

        dp[0] = 0;

        for (int i = 1; i <= maxDay; i++) {
            boolean check = false;
            for (int j = 0; j < length; j++) {
                if(days[j] == i){
                    check = true;
                    break;
                }
            }

            if(check){
                dp[i] = Math.min(dp[i-1] + costs[0], dp[Math.max(0, i - 7)] + costs[1]);
                dp[i] = Math.min(dp[i], dp[Math.max(0, i - 30)] + costs[2]);
            }else{
                dp[i] = dp[i -1];
            }
        }
        
        return dp[maxDay];
    }
}