[프로그래머스] 매출 하락 최소화 / 파이썬 / DP

programmers.co.kr/learn/courses/30/lessons/72416

확실히 어렵네요..

개인적으로 2021 카카오 문제중 가장 어려웠고, 알고리즘 공부를 열심히 해야겠다고 느꼈던 문제입니다..

DP문제인데, 생각보다 구현방법이 잘 안떠올라 답안을 보았습니다.

우선 Root는 1번이니, 1번부터 탐색을 시작합니다.

케이스는 두가지 입니다

1) dp[n][1] => n번 사람이 선발되는 경우
2) dp[n][0] => n번 사람이 선발되지 않는 경우

1번 케이스의 경우에는 쉽게 생각할 수 있는데요. n번의 매출액을 더하고 n번의 자식들이 선발이 되든, 안되든 최소값만 선택하면 됩니다.

2번 케이스의 경우 조금 까다롭습니다.
n번의 매출액을 더하지 않고, n번의 자식들이 선발이 되든, 안되든 최소값만을 선택하면 됩니다.

하지만, 모든 자식들이 선발되지 않는 케이스는 없어야 합니다!

그 경우를 flag를 주어서 처리했습니다.
만약 모든 자식들이 선발되지 않는 경우는 방문한 경우와, 방문을 하지 않은 경우의 차이값이 가장 작은 녀석을 선택해줍니다.
왜냐면 그 경우가 매출액 손해가 가장 적은 경우이거든요.

말을 하기는 쉬운데, 막상 코드를 짜면 또 어려운 문제였습니다.

그래도 코드를 보시면 이해하실 수 있으실 것입니다.

from copy import deepcopy
import sys

cost = None
dp = None
tree = None
INF = sys.maxsize

# n번이 선발되는 경우, 안되는 경우 분기 처리
def dfs(n, include):
    global cost, dp, tree

    if dp[n][include] != -1:
        return dp[n][include]

    ret = 0
    if include:
        ret = cost[n]
        for child in tree[n]:
            c_cost = min(dfs(child, 0), dfs(child, 1))
            ret += c_cost
        # print(n, include, ret)
        dp[n][include] = ret
        return dp[n][include] 
    else:
        # 내가 포함되지 않았다면 하위직원 중 하나는 무조건 있어야 함.
        ans = 0
        diff = 0 if len(tree[n]) == 0 else INF
        # 자식이 모두 참여 안하면, flag = False
        flag = False

        for child in tree[n]:
            cost1 = dfs(child, 1)
            cost2 = dfs(child, 0)
            # 방문한 코스트가 방문안한 코스트보다 작다 => 자식 중 방문한 케이스가 존재함을 의미, flag = True
            if cost1 < cost2:
                flag = True
            else:
                diff = min(cost1 - cost2, diff) 
            ans += min(cost1, cost2)
        ret = ans if flag else diff + ans
        dp[n][include] = ret
        return dp[n][include] 

def solution(sales, links):
    global dp, tree, cost
    answer = 0
    sales = [-1] + sales
    cost = sales 
    tree = [[] for _ in range(len(sales))]
    dp = [[-1, -1] for _ in range(len(sales))]
    # dp[n][1] n번이 선발되는 경우
    # dp[n][0] n번이 선발되지 않는 경우

    for p, c in links:
        tree[p].append(c)

    return min(dfs(1,1), dfs(1, 0))