[LeetCode] 309. Best Time to Buy and Sell Stock with Cooldown

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

Best Time to Buy and Sell Stock with Cooldown - LeetCode

Best Time to Buy and Sell Stock with Cooldown

 

 

그날 그날의 주식 가격이 vector로 들어와있다.

하루하루 세가지 동작 중 하나만 취할 수 있는데,

 

1. 사거나

2. 팔거나

3. 쉬거나

 

이다.

 

주의점은 세가지 동작 중 하나만 취할 수 있고, 주식을 들고 있는 상태에서는 또 살 수 없다.

마지막으로 주식을 팔면 그 다음날은 무조건 쉬어야한다.

 

이 때, 우리가 마지막날 얻을 수 있는 최대 수익을 구하는 문제다.

 

문제의 설명이 보기에 간단한고 형태를 보니 dp라는 생각이 딱 들었다.

문제는 점화식을 어떻게 세우냐..인데 고민을 좀 많이했다.

 

풀이는 아래와 같다.

각 날짜에 대한 상태는 세가지로 정할 수 있다.

 

1. 주식을 들고 있는 상태

2. 주식이 없는 상태 (판 다음날 제외)

3. 쉬어야만 하는 상태

 

이를 가지고 식을 세워보자.

1번 상태는 이미 주식을 사놓았거나, 주식이 없는 상태에서 그날 바로 주식을 살때 가능하다.

2번 상태는 쉬어야만 하는 상태에서 지나거나 주식이 없는 상태에서 그대로 있을 경우 가능하다.

마지막으로 3번상태는 주식을 들고 있는 상태에서 그날 바로 주식을 팔때 가능하다.

 

이를 이용하면,

그날 최대 수익을 얻기위해서는

max(1번 상태, 2번 상태, 3번 상태) 가 될 것이고,

그날 1번 상태에서 최대일경우 = max(1번상태, 2번상태-price)

그날 2번 상태에서 최대일경우 = max(2번 상태, 3번 상태)

그날 3번 상태에서 최대일경우 = max(1번상태+price)

로 나타낼 수 있다.

 

아래는 전체 풀이 코드이다

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int stock_y=INT_MIN, stock_n=0, cool=0;
        for (int price:prices) {
            int temp = cool;
            stock_y = max(stock_y,stock_n-price);
            cool = stock_y+price;
            stock_n = max(stock_n, temp);
        }
        return max(stock_y, max(cool, stock_n));
    }
};