[프로그래머스] - 매출 하락 최소화 (LEVEL 4)

programmers.co.kr/learn/courses/30/lessons/72416?language=python3#

코딩테스트 연습 - 매출 하락 최소화

트리dp 문제였다. dp문제라고 생각하긴 했지만 각 팀장이 참석 하는경우/하지 않는 경우로 나누어 풀 생각을 하지 못했다. 아직 dp 문제에 더 익숙해질 필요가 있을 것 같다.

 

dfs로 먼저 리프노드까지 탐색 후 리프노드부터 최적해를 찾아 올라온다.

root 노드부터 연결된 노드부터 탐색해가면서,

리프노드에서는 해당 노드를 선택했을 경우/ 선택하지 않았을 경우 두 가지 경우에 대한 값을 갱신해준다.

리프노드의 부모 노드는 해당 노드를 선택하고 리프노드를 선택하지 않았을 경우/ 해당 노드를 선택하지 않고 리프노드를 선택했을 경우에 대한 값을 갱신 이렇게 루트노드까지 올라왔을 때

루트 노드를 선택 했을 경우/ 선택하지 않았을 경우 중 작은 값을 return 하면 된다.

<Solution1>

def solution(sales, links):
    link=[[] for _ in sales]
    dp=[[0,0] for _ in sales]
    for a,b in links: link[a-1].append(b-1)
    def solve(i):
        sum_child=0
        for k in link[i]: 
            solve(k)
            sum_child+=min(dp[k][0],dp[k][1])
        dp[i][1]=sum_child + sales[i]
        if any(dp[k][0]>dp[k][1] for k in link[i]):
            dp[i][0]=sum_child
        else:
            dp[i][0]=sum_child + min(
            (dp[k][1]-dp[k][0] for k in link[i]),
            default=0)
    solve(0)
    return min(dp[0][0],dp[0][1])

 

<Solution2>

"""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(min_sales(0, True), min_sales(0, False))