1. 문제 소개

3573. Best Time to Buy and Sell Stock V

2. 나의 풀이

조금 지쳐서 혼자 힘으로 풀지 못했다.

3. 다른 풀이

dp를 사용하여 풀이가 이루어졌다.
사실 혼자 생각해서 풀 수 있는 문제였고, 욕심이 생겼지만 풀지 못했다.
아쉽다.
시간복잡도는 $O(n*k)$이다.

class Solution:
    def maximumProfit(self, prices: List[int], k: int) -> int:
        first_price = prices[0]  # 0일차 주가 (초기 상태 구성에 사용)

        # dp[trans] = [state0, state1, state2]
        # - state0: 거래 trans번까지 고려했을 때의 "현재 최대 이익" (포지션이 없는 상태로 해석 가능)
        # - state1: 거래 trans번 상태에서의 "매수(롱) 포지션" 관련 최적값 (현금-주식 형태의 보유 상태)
        # - state2: 거래 trans번 상태에서의 "반대 포지션/대체 상태" 관련 최적값 (문제 정의의 상태 전이에 의존)
        #
        # 초기값:
        # - state0 = 0
        # - state1 = -first_price
        # - state2 = first_price
        # 위 초기화는 day=0에서 가능한 상태의 기준값을 세팅하는 역할을 한다.
        dp = [[0, -first_price, first_price] for _ in range(k + 1)]

        n = len(prices)  # 전체 날짜 수
        
        # 1일차부터 마지막 날까지 순회하며 DP 갱신
        for day in range(1, n):
            curr_price = prices[day]  # 현재 날짜의 주가

            # trans를 k -> 1로 역순 갱신:
            # - dp[trans]를 갱신할 때 dp[trans-1]의 "이전 날짜 값"을 안정적으로 참조하기 위함
            for trans in range(k, 0, -1):
                prev_profit = dp[trans - 1][0]  # 바로 이전 거래 횟수 상태의 state0(기준 이익)

                # state0 갱신:
                # - 기존 state0 유지
                # - state1 + curr_price: state1(보유 상태)에서 curr_price로 청산하는 전이
                # - state2 - curr_price: state2 상태에서 curr_price로 전이하는 케이스(문제의 상태 정의에 의존)
                dp[trans][0] = max(
                    dp[trans][0],
                    dp[trans][1] + curr_price,
                    dp[trans][2] - curr_price
                )

                # state1 갱신:
                # - 기존 state1 유지
                # - prev_profit - curr_price: (trans-1)의 이익에서 curr_price로 진입(매수)하는 전이
                dp[trans][1] = max(dp[trans][1], prev_profit - curr_price)

                # state2 갱신:
                # - 기존 state2 유지
                # - prev_profit + curr_price: (trans-1)의 이익에서 curr_price로 진입하는 다른 전이(문제의 상태 정의에 의존)
                dp[trans][2] = max(dp[trans][2], prev_profit + curr_price)
        
        # k번 거래까지 고려했을 때의 최종 최대 이익(state0)을 반환
        return dp[k][0]

4. 마무리

오늘은 혼자 힘으로 풀지 못했다.