[Leetcode/C++] 122_Best Time to Buy and Sell Stock II

문제는 다음과 같습니다.

처음에는 dp로 접근해서 배열에 모든 경우의 수에 대해 저장하는 방법으로 풀었다가 겁나게 삽질했다 ㅠㅠ
2차원 배열에 i번째 날에 buy j번째 날에 sell 하는 식으로 일일이 구하고 뭐 그런식으로 했지만 이게 아닌 것 같아서 다른 방법을 찾았다.

일단, 몇몇의 예시를 써놓고 방법을 찾았는데
그림으로 입력받은 금액의 그래프를 그려보니 쉽게 문제를 풀 수 있었다.

먼저, 1번의 예시처럼 금액이 오르락내리락을 반복하는 경우를 보면,
구하는 최대 이익은 "증가하는 직선의 y좌표 값"을 구하면 된다.
여기서 "증가하는 직선"이란 ↗️이 방향의 직선을 의미한다.
왜냐하면 주식을 먼저 사고 이후에 팔아야하므로 그리고 이 이익이라는것은 양수값이어야만 하니까, ↗️ 이 방향 그래프의 y절편의 최대-최소값이 이익이 된다.
1번의 예시를 보면, ↗️이 방향 그래프가 나타나는 부분은 (1,5) 그리고 (3,6) 두 가지 경우이며, 따라서 4+3=7이 답이 된다.

그리고 두 번째 예시를 살펴보면 이 경우는 부분적으로 계속 증가하는 경우이다. 이 경우가 예외라고 생각할 수도 있겠지만, 1번 경우를 응용하면 된다.
즉, ↗️이 방향 그래프가 연속적으로 나온다고 생각하면 된다.

원래 2번과 같은 경우의 답은 (1, 100) 이어서 100-1=99가 주어진 답의 풀이가 된다.
하지만 이는 ↗️방향 그래프가 두 개인 (1, 5), (5, 100)이 두 번 있다고 생각하면 되고,
이는 4+95=99로 답과 같게 나오게 된다.

이 두 번째 예시 때문에,
for문 코드를 살펴보면

        for(int i=1; i<prices.size(); i++){
            buy_cost=min(buy_cost, prices[i]);
            if(prices[i]>buy_cost){
                profit+=(prices[i]-buy_cost);
                buy_cost=prices[i];
            }
        }

다음과 같은데,
여기서 if문안의 buy_cost가 prices[i+1]이 아니라 buy_cost=prices[i]가 된다.

어차피, buy_cost=min(buy_cost, prices[i])에서 더 작은 값으로 갱신해주기때문에 상관이 없게 된다.

전체 코드는 다음과 같다.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy_cost=prices[0];
        int profit=0;
        
        for(int i=1; i<prices.size(); i++){
            buy_cost=min(buy_cost, prices[i]);
            if(prices[i]>buy_cost){
                profit+=(prices[i]-buy_cost);
                buy_cost=prices[i];
            }
        }
        return profit;
    }
};

---

2/8 화요일 복습)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 증가하는 구간만 다 구하면 됨
        int buy_cost = prices[0];
        int profit, total=0;
        for(int i=1; i<prices.size(); i++){
            buy_cost = min(buy_cost, prices[i]);
            profit = max(0, prices[i]-(buy_cost)); // 음수여도 0을 더할 수 있도록
            total += profit;
            buy_cost = prices[i]; // buy_cost 갱신시키기
        }
        return total;
    }
};