[릿코드 638] Shopping Offers (파이썬/python)

https://leetcode.com/problems/shopping-offers/description/

Shopping Offers - LeetCode

 

상당히 시간을 많이 쓴 문제;

스페셜 오퍼를 넣는 모든 상황을 dfs 로 순회하며 문제를 풀어야한다.

 

메모이제이션을 안하면 도무지 시간초과를 피할수가없어서 딕셔너리를 이용한 메모이제이션을 사용했다.

 

내 코드를 보면 모든 spacial 판매를 구매하는 경우를 탐색하는데

이 spacial offer 를 차감한 current_need 를 스트링으로 변환한 후 메모이제이션 딕셔너리의 키로 활용했다.

 

어떤 경우에라도 같은 수량이 남았을 경우엔 훨씬 저렴한 가격을 탐색한 적이 있다면
그 이후의 탐색은 의미가없다.

 

class Solution:
    result_price = 0

    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
        # 메모이제이션 딕셔너리, 여러 경우에따라 필요한 항목 리스트가 같은 경우가 있는데
        # 필요한 항목 리스트의 문자열을 키로 가지고 가격을 판단한다.
        dp = {}
        for i in range(len(price)):
            self.result_price += price[i] * needs[i]

        def dfs(need, cost, s):

            for i in range(s, len(special)):
                flag = True
                row_cost = 0
                current_need = need[:]
                for j in range(len(current_need)):
                    if current_need[j] < special[i][j]:
                        flag = False
                        break
                    current_need[j] -= special[i][j]
                    row_cost += current_need[j] * price[j]

                if flag:
                    current_cost = special[i][-1] + cost + row_cost
                    # 메모이제이션 키
                    key = str(current_need)
                    # 메모이제이션 확인
                    if dp.get(key) and dp.get(key) <= current_cost:
                        continue
                    self.result_price = min(self.result_price, current_cost)
                    # 메모이제이션
                    dp[key] = current_cost
                    dfs(current_need, cost + special[i][-1], i)

        dfs(needs, 0, 0)
        return self.result_price