[DP: Unbounded Knapsack] 983. Minimum Cost For Tickets

983. Minimum Cost For Tickets

 

https://youtu.be/4pY1bsBpIY4?si=PbuLW3CZC5vqdJDg

 

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        # ✅ dp[i]는 i번째 여행일(day[i])부터 시작할 때 필요한 최소 비용을 저장
        dp = {}

        # dfs(i): days[i]일부터 여행을 시작할 때 필요한 최소 비용을 반환
        def dfs(i):
            # 종료 조건: 모든 여행일을 다 처리한 경우 → 추가 비용 없음
            if i == len(days):
                return 0

            # 이미 계산한 결과가 있으면 바로 반환 (메모이제이션)
            if i in dp:
                return dp[i]

            # 현재 위치에서 가능한 최소 비용을 구하기 위해 무한대로 초기화
            dp[i] = float("inf")

            # 각각의 티켓(costs)과 그 유효 기간([1, 7, 30])을 짝지어 반복
            for cost, pass_days in zip(costs, [1, 7, 30]):
                j = i

                # 티켓이 유효한 동안 커버되는 날(days[j])들을 건너뛰기
                # days[i] + pass_days 전까지는 커버되므로 j를 증가
                while j < len(days) and days[j] < days[i] + pass_days:
                    j += 1

                # j번째 날부터 다시 dfs 시작 + 현재 티켓 비용을 더함
                dp[i] = min(dp[i], dfs(j) + cost)

            # i번째 날부터 시작했을 때의 최소 비용 반환
            return dp[i]

        # 여행의 첫 날부터 시작
        return dfs(0)

 

🧠 핵심 개념 요약

요소	설명
dp[i]	days[i]부터 여행을 시작할 때 필요한 최소 비용
zip(costs, [1, 7, 30])	각 티켓(1일권, 7일권, 30일권)과 가격(costs)을 묶어서 반복
while j < len(days) and days[j] < days[i] + pass_days	현재 티켓이 커버하는 마지막 날까지 j를 옮겨서 다음 구매일 계산
dfs(j) + cost	j일 이후부터 다시 dfs 시작하고, 지금 산 티켓 비용을 더함

특히, 

# j번째 날부터 다시 dfs 시작 + 현재 티켓 비용을 더함
dp[i] = min(dp[i], dfs(j) + cost)

 

이부분은 while 문 안으로 들어가도 됨

그래서, 정상 동작은 하지만, 

 j가 업데이트된 후에만, dfs(j)를 호출해야 티켓 유효기간 이후의 날부터 새로 dfs를 시작하기 때문에

while 루프로 j를 이동한 다음에, dfs(j) + cost로 dp[i]를 갱신하는 것이 더 맞음

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        # ✅ dp[i]는 i번째 여행일(day[i])부터 시작할 때 필요한 최소 비용을 저장
        dp = {}

        # dfs(i): days[i]일부터 여행을 시작할 때 필요한 최소 비용을 반환
        def dfs(i):
            # 종료 조건: 모든 여행일을 다 처리한 경우 → 추가 비용 없음
            if i == len(days):
                return 0

            # 이미 계산한 결과가 있으면 바로 반환 (메모이제이션)
            if i in dp:
                return dp[i]

            # 현재 위치에서 가능한 최소 비용을 구하기 위해 무한대로 초기화
            dp[i] = float("inf")

            # 각각의 티켓(costs)과 그 유효 기간([1, 7, 30])을 짝지어 반복
            for cost, pass_days in zip(costs, [1, 7, 30]):
                j = i

                # 티켓이 유효한 동안 커버되는 날(days[j])들을 건너뛰기
                # days[i] + pass_days 전까지는 커버되므로 j를 증가
                while j < len(days) and days[j] < days[i] + pass_days:
                    j += 1
                    # j번째 날부터 다시 dfs 시작 + 현재 티켓 비용을 더함
                    dp[i] = min(dp[i], dfs(j) + cost)

            # i번째 날부터 시작했을 때의 최소 비용 반환
            return dp[i]

        # 여행의 첫 날부터 시작
        return dfs(0)

 

💡 결론

• while 안에서 dp[i] = min(...) 하는 건 가능하지만 헷갈리기 쉬움
• 보통은 while로 j 값을 먼저 계산한 후,
  dp[i] = min(dp[i], dfs(j) + cost) 를 while 밖에서 처리하는 게 더 깔끔하고 명확함