[Medium] 122. Best Time to Buy and Sell Stock II

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

 

Q. stock의 가격 prices 배열이 주어진다. 하루에 하나씩 팔거나 혹은 살 수 있고, 한번에 하나의 stock만들 가질 수 있을 때, 최대의 수익을 구하라. 

 

 

Solution.

 우선 매일(모든 index)위치에서 팔거나 혹은 사거나 아니면 아무것도 안하거나의 세개의 action이 가능하다. 

 다만, 이전에 샀으면 이번에는 팔기만 가능하며, 안샀으면 사기만 가능하다.

 따라서 이전 조건에 따라 각 2가지만 가능하다. 

 

 이대로 DP로 접근 해 본다.

 

 DP의 핵심은 이전 누적값에 영향을 받지 않게, 특정 위치에서 독립적으로 끝까지 계산한 결과를 갖도록 로직을 만들어야 하는 것이다. 

 즉, 이전까지 사온 누적 이익 이런것들을 로직에 넣으면, 전체 로직을 돌아갈 수 있으나, 최적화가 불가능해 진다. (cache 불가.)

 따라서 각 특정 위치에서 독립적으로 생각해 본다. 

 

 prices를 지난 위치면, 거래가 불가능하므로 0을 반환하면 된다.  => if(curIdx >= prices.size())     return 0

 

 마지막 위치에서 생각해 보자.

 우선, 이전 구매 주식에 관계없이 아무 행동도 안 할 수 있다. (물론 샀다면 파는게 이익이겠지만, 팔지 않았으므로 절대 최대 이익은 될수 없을 것이다.)

 산 주식이 있다면, 팔 수 있다. 

 산 주식이 없다면 사기만 가능하다. 

  

 아무 행동도 안한다. => return 0 + next_dp(index+1)

 판다 => if(hasStock) return prices[idx] + next_dp(index+1, false(hasStock))    // 다음 dp 함수에 현재 구매 여부 인자로 넘김.

 산다 => return -prices[idx] + next_dp(index+1, true(hasStock))

 

 이후로는 어느 위치에서도 이 로직이 그대로 적용됨을 알 수 있다. 

 

 이를 코드로 만들어 본다. 

 

 

int profit(vector<int>& vCache, vector<int>& prices, int idx, bool bought)
{
    if(idx >= prices.size())
        return 0;

    int idxCache = prices.size()*(bought ? 1 : 0) + idx;
    if(vCache[idxCache] >= 0)
        return vCache[idxCache];

    int stay = profit(vCache, prices, idx+1, bought);

    if(bought)
    {
        // stay or sell.
        int sell = prices[idx] + profit(vCache, prices, idx+1, false);
        return vCache[idxCache] = max(stay, sell);
    }
    else
    {
        // stay or buy
        int buy = -prices[idx] + profit(vCache, prices, idx+1, true);
        return vCache[idxCache] = max(stay, buy);
    }
}

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

 

 적절한 결과를 얻었다. 

 

Note ) 그냥 로직 정리가 아닌, DP 방식으로 수식을 정리하는 법을 잘 알아야 한다.!