638. Shopping Offers

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

Shopping Offers - LeetCode

음.. 요즘에는 예전과는 다르게,

최적 값 찾는 문제를 테이블로 어떻게 접근할 것인지 부터 생각하고있네

예전엔 반대였는데

 

아무튼, 긍정적인 신호고

 

반대로 DP문제에서 테이블 접근에 있어서 답이 도저히 안나 올 때는

그냥 직관적으로 recursion을 이용해 코드를 풀어 쓰고,

 

memoization을 적용하면 의외로 쉽게 풀릴 수도 있다.

 

첫 시도에서 실패

class Solution:
    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
        
        memo = dict()
        
        # return minimum cost to meat the target
        def dfs(targets):
            if tuple(targets) in memo:
                return memo[targets]
            
            ret = float('inf')
            best_after_using = None
            
            use_any_offer = False
            for offer in special:
                counts = offer[:-1]
                price_offer = offer[-1]
                
                can_use = True
                after_using = [0]*len(targets)
                for i, c in enumerate(counts):
                    if c > targets[i]:
                        can_use = False
                        break
                    after_using[i] = targets[i]-c
                
                if not can_use:
                    continue
                
                trial = dfs(after_using)+price_offer
                if trial < ret:
                    ret = trial
                
                use_any_offer = True
            
            if not use_any_offer:
                ret = 0
                for i, c in enumerate(targets):
                    if c <= 0:
                        continue
                    ret += c * price[i]
            
            memo[tuple(targets)] = ret
            return ret
        
        return dfs(needs)

offer를 이용하지 않고 해결하는 코드를

위로 올려줬다.

 

성공

 

84ms, 84%!!!

class Solution:
    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
        
        memo = dict()
        
        # return minimum cost to meat the target
        def dfs(targets):
            if tuple(targets) in memo:
                return memo[tuple(targets)]
            
            ret = 0
            for i, c in enumerate(targets):
                if c <= 0:
                    continue
                ret += c * price[i]
            
            use_any_offer = False
            for offer in special:
                counts = offer[:-1]
                price_offer = offer[-1]
                
                can_use = True
                after_using = [0]*len(targets)
                for i, c in enumerate(counts):
                    if c > targets[i]:
                        can_use = False
                        break
                    after_using[i] = targets[i]-c
                
                if not can_use:
                    continue
                
                trial = dfs(after_using)+price_offer
                if trial < ret:
                    ret = trial
                
                use_any_offer = True
            
            memo[tuple(targets)] = ret
            return ret
        
        return dfs(needs)

 

50ms (top solution)

class Solution:
    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
        cache = {}
        def help(price, special, needs):
            if tuple(needs) in cache:
                return cache[tuple(needs)]
            
            cost=0
            for p, n in zip(price, needs):
                cost += p*n
            
            for offer in special:
                for n_need, n_offer in zip(needs, offer):
                    if n_offer > n_need:
                        break
                else:
                    new_needs = [need - offer[i] for i, need in enumerate(needs)]
                    cost = min(cost, offer[-1] + help(price, special, new_needs))
            cache[tuple(needs)] = cost
            return cost
        
        return help(price, special, needs)