====== 매출 하락 최소화 ======

===== 풀이 =====
  * 트리에서의 DP를 이용하는 문제. 
  * 사실 내가 푼 아래 코드와 [[https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/|공식 풀이]]가 거의 일치한다. 그래서 풀이는 생략.
  * DP table을 명시적으로 만드는 대신 functools.lru_cache를 붙이는 것으로 처리했다.

===== 코드 =====
<dkpr py>
"""Solution code for "Programmers 72416. 매출 하락 최소화".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/72416
- Solution link: http://www.teferi.net/ps/problems/programmers/72416
"""

import functools


def solution(sales, links):

    @functools.lru_cache(maxsize=None)
    def min_sales(node, should_include_root):
        children_sum = sum(min_sales(c, False) for c in children[node])
        sales_including_root = sales[node] + children_sum
        if should_include_root:
            return sales_including_root
        sales_without_root = children_sum + min(
            (min_sales(c, True) - min_sales(c, False) for c in children[node]),
            default=0)
        return min(sales_including_root, sales_without_root)

    children = [[] for _ in sales]
    for a, b in links:
        children[a - 1].append(b - 1)
    return min_sales(0, False)

</dkpr>

{{tag>프로그래머스 ps:problems:programmers:Level_4}}