[Leetcode] 2944. Minimum Number of Coins for Fruits

https://leetcode.com/problems/minimum-number-of-coins-for-fruits/description/

과일 사는데 코인 가능한 적게 뽑기 문제이다. 판매하는 사람이 혜자로워서 하나 사면 옆에 있는 과일 i+1개 만큼은 공짜로 준다고 한다. 그래서 가능한 코인 적게 사기 문제이다.

도저히 방법ㅇ르 못찾겠어서 solution보고 풀었다. monotone stack이라는 방법이라고 한다.

class Solution:
    def minimumCoins(self, prices: List[int]) -> int:
        temp = [(0,0)]
        for i in range(len(prices)):
            pos,new = 2 * i + 2, temp[0][1] + prices[i]
            if i == temp[0][0]:
                temp.pop(0)
            while temp:
                if temp[-1][1] >= new:
                    temp.pop()
                else:
                    break
            temp.append((pos,new))
        return temp[0][1]                

처음에 temp에 (0, 0)으로 초기화 해준 뒤, 반복을 시작한다.
pos는 공짜로 구매할 수 있는 최대 index를 저장하고, new에는 i과일을 구매한 총 가격을 저장한다.

i가 temp의 첫번째 index와 일치하면 삭제하고 아니라면 temp를 뒤에서부터 돌면서 가격이 new보다 큰 것들을 제거한다.
그리고 새로운 가격을 추가해준다.