99클럽 코테 스터디 25일차 TIL Leetcode Minimum Number of Coins for Fruits

나의 접근 방법

처음에는 주어진 태그였던 스택으로 생각해보았다가, 문제를 읽으면서, dp로 풀어야겠다는 생각을 했다.

문제는 다음과 같다.

i 번째 과일을 사면, 그 다음에 오는 i+1 개의 과일들을 모두 공짜로 가져갈 수 있다. 공짜로 가져갈 수 있는 과일들이라도, 여전히 살 수 있다. 모든 과일들을 가져갈때, 최소한의 비용을 구하시오.

내가 생각했던 논리는 다음과 같다.

i+1번째 과일을 사서 모두 가져가려면, i번째까지 과일들은 i번째에 과일을 샀거나 안샀거나 중 하나이고, i+1번째 과일을 안사면서 모두 가져가려면, 이전 k번째에서 k+1개의 과일들을 가져가는 범위에 i+1번째 과일이 속해있어야 한다.

 

나의 코드

처음 풀때는 단순히 i번째 과일을 살때 뒤에 i+1개의 과일들에 최소값을 반영하는 식으로 풀었다.

시간복잡도 : O(N**2)

class Solution:
    def minimumCoins(self, prices: List[int]) -> int:
        N=len(prices)
        dp=[[float("inf"),float("inf")] for _ in range(N)]
        dp[0][0]=prices[0]
        for i in range(N):
            for j in range(i+1,2*(i+1)):
                if j<N:
                    dp[j][0]=min(dp[j][0],dp[i][0]+prices[j],dp[j-1][1]+prices[j])
                    dp[j][1]=min(dp[j][1],dp[i][0])
                else:
                    break
        return min(dp[-1])

개선된 코드 

런타임 상위에 기록된 코드들을 참고하여 작성한 코드.

큐를 활용하여, 최소의 값으로 모든 과일을 사도록 어디까지 무료로 살 수 있는지 기록하면서 더해준 풀이이다.

시간복잡도 : O(N)

from collections import deque
class Solution:
    def minimumCoins(self, prices: List[int]) -> int:
        queue=deque()
        queue.append((0,0))
        for i in range(len(prices)):
            free_until,buy_i=(i+1)*2,queue[0][1]+prices[i]
            if i==queue[0][0]:
                queue.popleft()
            while queue:
                if queue[-1][1]>=buy_i:
                    queue.pop()
                else:
                    break
            queue.append((free_until,buy_i))
        return queue[0][1]