1. 문제 소개

3562. Maximum Profit from Trading Stocks with Discounts

2. 나의 풀이

혼자 힘으로 풀지 못했다.

3. 다른 풀이

dfs와 dp를 사용한 다른 풀이를 보았다.
사실 아래 풀이를 다 이해하지도 못했다.

class Solution:
    def maxProfit(self, n: int, present: List[int], future: List[int], hierarchy: List[List[int]], budget: int) -> int:
        adj_list = defaultdict(list)  # 부모 -> 자식 인접 리스트
        for h in hierarchy:
            adj_list[h[0] - 1].append(h[1] - 1)  # 입력은 1-indexed이므로 0-indexed로 변환
        
        @lru_cache(None)
        def dfs(employee, has_discount):
            # employee 노드에서 시작해 서브트리 내에서 가능한 (spent -> profit) 최적값 맵을 반환
            # has_discount가 True이면 현재 노드 구매 비용을 절반으로 적용
            cost = present[employee] // 2 if has_discount else present[employee]  # 현재 노드 구매 비용
            profit = future[employee] - cost  # 현재 노드 1개를 구매했을 때의 순이익
            
            # buy_current: 현재 노드를 "구매"하는 경우의 (지출 -> 이익) 맵
            # - cost <= budget일 때만 구매 가능
            buy_current = {cost: profit} if cost <= budget else {}
            # skip_current: 현재 노드를 "구매하지 않음"의 (지출 -> 이익) 맵 (항상 0:0으로 시작)
            skip_current = {0: 0}
            
            # 자식 서브트리들을 하나씩 결합(배낭식 컨볼루션)하여 경우의 수를 확장
            for child in adj_list[employee]:
                # 현재 노드를 구매하는 경우: 자식은 할인(True)을 받는 케이스의 dfs 결과를 결합
                child_with_discount = dfs(child, True)  # Do something
                # 현재 노드를 스킵하는 경우: 자식은 할인(False)을 받지 않는 케이스의 dfs 결과를 결합
                child_no_discount = dfs(child, False) # Do nothing
                
                # buy_current(현재 구매) ⊗ child_with_discount(자식 할인) 결합
                new_buy = {}
                for spent, prof in buy_current.items(): # Do something, but the current stock
                    for child_spent, child_prof in child_with_discount.items():
                        total_spent = spent + child_spent  # 합산 지출
                        if total_spent <= budget:          # 예산 이내만 유지
                            total_prof = prof + child_prof # 합산 이익
                            # 동일 지출(total_spent)에 대해 최대 이익을 유지
                            if total_spent not in new_buy or new_buy[total_spent] < total_prof:
                                new_buy[total_spent] = total_prof
                buy_current = new_buy # This is mandatory because you need to check 
                                      # all possible combinations of picking children results. 
                                      # For example if the given graph is 1 -> 2, and 1 -> 3, 
                                      # it might be correct to either pick the path from 1 to 2, 
                                      # the path 1 to 3, or both paths if there is still budget left. 
                                      # Same goes for a skipping action.
                
                # skip_current(현재 스킵) ⊗ child_no_discount(자식 할인 없음) 결합
                new_skip = {}
                for spent, prof in skip_current.items(): # Do nothing, skip the current stock
                    for child_spent, child_prof in child_no_discount.items():
                        total_spent = spent + child_spent  # 합산 지출
                        if total_spent <= budget:          # 예산 이내만 유지
                            total_prof = prof + child_prof # 합산 이익
                            # 동일 지출(total_spent)에 대해 최대 이익을 유지
                            if total_spent not in new_skip or new_skip[total_spent] < total_prof:
                                new_skip[total_spent] = total_prof
                skip_current = new_skip
            
            # 현재 노드에서의 최종 결과: "구매"와 "스킵" 두 맵을 합쳐 지출별 최대 이익을 유지
            result = {} # Merge the results of doing something and doing nothing at node employee
            for spent, prof in buy_current.items():
                if spent not in result or result[spent] < prof:
                    result[spent] = prof
            for spent, prof in skip_current.items():
                if spent not in result or result[spent] < prof:
                    result[spent] = prof
            
            return result
        
        # 루트(0번 직원)에서 시작, 루트는 할인 없이(False) 시작
        result = dfs(0, False)
        # 가능한 지출들 중 최대 이익을 반환 (없으면 0)
        return max(result.values()) if result else 0

4. 마무리

이번 문제는 손도 못대 슬프다.