매출 하락 최소화
https://school.programmers.co.kr/learn/courses/30/lessons/72416
문제 설명
그림의 조직도는 다음과 같이 설명할 수 있습니다.
원 안에 적힌 두 개의 숫자는 직원의 정보를 담고 있습니다. 왼쪽 숫자는 직원번호이며 오른쪽 숫자는 해당 직원의 하루평균 매출액을 나타냅니다. 위 그림에서 1번 직원은 14원을, 9번 직원은 28원의 하루평균 매출액을 기록하고 있습니다.
CEO를 포함하여 모든 직원은 팀장 또는 팀원이라는 직위를 가지고 있으며 그림에서는 팀장과 팀원의 관계를 화살표로 표시하고 있습니다. 화살표가 시작되는 쪽의 직원은 팀장, 화살표를 받는 쪽의 직원은 팀원을 의미합니다.
"제이지"는 자신이 구상한 새로운 사업 아이템에 대해 직원들에게 설명하고자 하루 일정으로 워크숍을 계획하고 있습니다. 워크숍에서 교육받은 내용은 전 직원들에게 공유되어야 하므로 모든 팀은 최소 1명 이상의 직원을 워크숍에 참석시켜야 합니다.
워크숍 기간 동안, 회사의 매출 손실을 최소화하는 것이 중요하므로 워크숍에 참석하는 직원들의 하루평균 매출액의 합이 최소가 되어야 합니다.
직원들의 하루평균 매출액 값을 담은 배열 sales, 직원들의 팀장-팀원의 관계를 나타내는 2차원 배열 links가 매개변수로 주어집니다. 이때, 모든 팀에서 최소 한 명 이상 워크숍에 참석하면서, 참석하는 직원들의 하루평균 매출액의 합을 최소로 하려고 합니다. 그렇게 최소화된 매출액의 합을 구해서 return 하도록 solution 함수를 완성해 주세요.
풀이 설명
문제를 읽으면 알겠지만, 그래프를 이용해 각각의 관계를 저장하고 최솟값을 찾는 문제다.
각 그래프를 탐색하며 dp를 통해 자신이 참석할 경우(dp[i][0])와 참석하지 않는 경우(dp[i][1])로 구분해 저장한 후 최솟값을 반환한다.
def solution(sales, links):
sales = [0] + sales
graph = [[] for _ in range(len(sales)+1)]
for x,y in links:
graph[x].append(y)
dp = [[0,0] for _ in range(len(sales)+1)] # 참가, 참가 x
DFS(1, dp, graph, sales)
return min(dp[1])
def DFS(node, dp, graph, sales):
if not graph[node]:
# 리프노드는 자신이 참가하지 않는다면 아무도 참가하지 않아 0이다
dp[node][0] = sales[node]
dp[node][1] = 0
return
dp[node][0] = sales[node]
min_gap = float('inf')
for n in graph[node]:
DFS(n, dp, graph, sales)
dp[node][0] += min(dp[n])
min_gap = min(min_gap, dp[n][0] - dp[n][1])
if min_gap < 0:
min_gap = 0
dp[node][1] = dp[node][0] + min_gap - sales[node]