문제 링크

나의 논리

이와 비슷한 그리디 알고리즘은 백준에서 많이 풀어봤는데 오랜만에 풀려고 하니까 또 못풀었다.

너무 어렵게 생각했을까..? 최적부분구조와 탐욕적 선택 속성을 선택 해 봤다. 앞의 선택이 후의 선택에 영향을 미치지 않고, 현재의 상태에서 최적값을 구한 후 모아서 결과값으로 도출한다.

i번째날에 주식을 사고 산 날의 가격보다 크다면 바로 판다. 주식을 팔았을때는 어떤 변수를 -1로 초기화 해놓고 변수가 -1이라면 주식의 가격과 상관없이 다음날부터 바로 산다. 이 과정을 반복했다. 그리고 오답이 나왔는데 생각해보니까 주식을 사고 -> 팔고는 하나의 트랜잭션이다. 그래서 주식을 사기만하거나 팔기만 할 수 없다.
그러나 사고 -> 팔고 -> 사고는 가능하다. 즉 같은 날에 팔고 다시 같은 날에 살 수 있다. 그리고 그 다음날 주식 가격이 오르면 다시 판다. 이것이 정답논리였다.

파이썬 코드

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        ret = 0
        for i in range(len(prices)-1):
            if prices[i+1] > prices[i]:
                ret += (prices[i+1] - prices[i])
                
        return ret

자바스크립트 코드

var maxProfit = function(prices) {
    
    let ret = 0;
    for(let i=0; i<prices.length-1; ++i){
        if(prices[i+1] > prices[i]){
            ret += (prices[i+1]-prices[i]);
        }
    }
    
    return ret
    
};