[DP-Multidimensional][Medium] 714. Best Time to Buy and Sell Stock with Transaction Fee.

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description

LeetCode - The World's Leading Online Programming Learning Platform

 

Q. 주어진 배열 prices에서 각 값은 그날 stock의 가격을 의미한다. 

 stock을 사고 팔때, fee의 비용이 발생한다면, 얻을 수 있는 최대 수익을 구하라. 

 

 

Solution. 

 우선 이 문제도 DP로 풀수 있다는 것을 기억해 두자. 

 

특정 날에 할수 있는 action에 대해 정리 해 보자. 

 이전에 산 stock이 없다면, 

   오늘 산다. 

   그냥 오늘은 지나친다. 

 

 이전에 산 stock이 있다면,  

   오늘 판다. (오늘 값이 더 싸서 수익이 마이너스 일수 있지만, 구하고자 하는 값은 최대값이므로, 결과에서 무시된다.)

   그냥 오늘 지나친다. 

 

로 정리가 된다. 

 

이를 로직으로 만들어 본다.

 

int maxProfit_dp(vector<int>& prices, int idx, bool canSell, const int fee)
{
    if (idx >= prices.size())
        return 0;

    if (canSell == false)
    {
        // 사거나 - 사는 시점에 현재 가격을 차감에 유의.
        // 안사거나
        return max(-prices[idx]+maxProfit_dp(prices, idx + 1, true, fee), 
                   maxProfit_dp(prices, idx + 1, false, fee));
    }
    else
    {
        // 팔거나 - 수익 계산에 유의
        // 안팔거나
        return max(prices[idx] - fee + maxProfit_dp(prices, idx + 1, false, fee),
                  maxProfit_dp(prices, idx + 1, true, fee));
    }
}
public:
    int maxProfit(vector<int>& prices, int fee) {
        return maxProfit_dp(prices, 0, false, fee);
    }

 

잘 작동하지만, 예상대로 TC가 초과된다. 최적화 하자.

 

 

 

int maxProfit_dp(vector<int>& vCache, vector<int>& prices, int idx, bool canSell, const int fee)
{
    if (idx >= prices.size())
        return 0;

    int idxCache = idx;

    if (canSell == false)
    {
        if(vCache[idxCache] >= 0)   return vCache[idxCache];
        vCache[idxCache] = max(
            maxProfit_dp(vCache, prices, idx + 1, true, fee) - prices[idx],
            maxProfit_dp(vCache, prices, idx + 1, false, fee));
    }
    else
    {
        idxCache += prices.size();
        if(vCache[idxCache] >= 0)   return vCache[idxCache];

        vCache[idxCache] = max(
            prices[idx] - fee + maxProfit_dp(vCache, prices, idx + 1, false, fee),
            maxProfit_dp(vCache, prices, idx + 1, canSell, fee));
    }

    return vCache[idxCache];
}

 int maxProfit(vector<int>& prices, int fee) 
{
    vector<int> vCache;
    vCache.resize(prices.size()*2, -1);
    return maxProfit_dp(vCache, prices, 0, false, fee);
}

 

 

결과. 

 

Note : 이번 문제는, 파는 시점에 최종 가격에 대한 계산을 하느라 오류를 겪었다. 그리되면, 문제는 풀리지만, 위와 같은 DP일반 최적화가 쉽게 되지 않는다.  

따라서 이전 event에 대한 정보를 현재 시점에 같이 계산하는 것이 아닌, 그 시점에 처리되야 할 내용은 처리하고 다음 동일 event로 넘기는 것이 중요하다. 

 

ex) stock 가격 =>

       Price(n) - boughtPrice - transaction fee + dp(n) : 파는 시점에 이렇게 계산하기보다, 

 

       -Price(n) + dp(n) : 사는 시점의 action

       Price(n) - transaction fee + dp(n) : 파는 시점의 action 

       해야 올바른 결과를 얻을 수 있다.