123. Best Time to Buy and Sell Stock III - Streak 20

첫날에 풀었던 문제의 변형판이다.

188. Best Time to Buy and Sell Stock IV - Streak 1

 

이 문제는 최대 2번의 트랜잭션만이 가능했다.

이전의 문제는 최대 k번의 트랜잭션만이 가능했고, k가 입력으로 주어지는 방식이라 좀 더 까다로운 문제였다.

한마디로 이번 문제가 좀 더 쉽다.

 

이전의 아이디어를 떠올려보자.

• 결국 주식은 팔아야 그 가치가 생긴다.
  • 즉, 주식을 '사는 행위'는 현재 가진 재산을 깎는 행위고,
    팔아야 실질적으로 사용할 수 잇는 재산으로 변모한다.
• 우리의 목적은 "재산을 최대화"하는 것에 있다.

이 두 가지 정보를 생각하며 간단하게 순회하는 시뮬레이션을 돌려보자.
한번만 팔 수 있다고 하면, 현재 인덱스 이전까지의 가장 저렴한 주식을 구매하고, 현재 시점에 그 주식을 판매하는 것이 현재 인덱스에서 가장 비싸게 얻는 수익일 것이다.

 

그럼 두 번째 판매 시점은 어떻게 될까?
같은 주식을 두번 판매할 수는 없기에, 이전 판매 시점 이후부터 현재 시점까지 가장 저렴한 주식을 찾아야 한다.

그런데 잘 생각해보면, 같은 주식을 "두번 이상 구매할 수 없다"는 제한은 다음과 같은 방식으로 해석이 가능하다.

• 시점 [A, B, C, D]가 있다고 했을 때, A 시점에 구입 후 C 시점에 판매했을 때의 수익이 B시점에 구입 후 C시점의 판매했을 때의 수익보다 높다면 D 시점에선 C-A만을 원하게 된다.
• A 시점에서 구입 후, B시점에서 또 구입하고 C 시점에서 판매할 수 없다.
  따라서 현재 인덱스에서 k-1번까지 판매했던 최대 수익에, 현재 인덱스의 주식을 구매하면 주어진 조건을 유지하며 주식을 구입할 수 있다.
  • 현재 인덱스에서 주식을 구입하면 미래 시점의 가격으로 판매 할 수 밖에 없다.

그럼 현재 시점의 최대 수익은 어떻게 구할 수 있을까?
이는 아래 식으로 정의할 수 있다.

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][3];
        for(int k = 1; k<=2; k++){
            int nowTake = -prices[0];
            for(int i = 1; i<n; i++){
                dp[i][k] = Math.max(dp[i-1][k], nowTake + prices[i]);
                nowTake = Math.max(nowTake, dp[i][k-1] - prices[i]);
            }
        }
        return dp[n-1][2];
    }
}