유통전문회사 카카오상사의 오너인 제이지는 새로운 사업 아이템을 구상하기 위해 전문경영인(CEO)인 프로도에게 회사의 경영을 부탁하였습니다. "카카오상사"는 직원들을 여러 개의 팀 단위로 조직을 구성하고 있으며 아래 그림은 CEO를 포함하여 10명의 직원과 4개의 팀으로 구성되어 있는 회사 조직도를 보여주고 있습니다.
그림의 조직도는 다음과 같이 설명할 수 있습니다.
1. 그림의 각 원들은 각각의 직원 1명을 표시하고 있으며, CEO를 포함하여 총 10명의 직원을 표시하고 있습니ek.
2. 원 안에 적힌 두 개의 숫자는 직원의 정보를 담고 있습니다. 왼쪽 숫자는 직원번호이며 직원을 식별할 수 있도록 1번부터 순서대로 발급되는 일련번호이며, 오른쪽 숫자는 해당 직원의 하루평균 매출액을 나타냅니다. 위 그림에서 1번 직원은 14원을, 9번 직원은 28원의 하루평균 매출액을 기록하고 있습니다.
3. CEO를 포함하여 모든 직원은 팀장 또는 팀원이라는 직위를 가지고 있으며 그림에서는 팀장과 팀원의 관계를 화살표로 표시하고 있습니다. 화살표가 시작되는 쪽의 직원은 팀장, 화살표를 받는 쪽의 직원은 팀원을 의미합니다.
3-1. CEO를 포함하여 모든 직원은 팀장 또는 팀원이라는 직위를 가지고 있으며 그림에서는 팀장과 팀원의 관계를 화살표로 표시하고 있습니다. 화살표가 시작되는 쪽의 직원은 팀장, 화살표를 받는 쪽의 직원은 팀원을 의미합니다
3-2. 직원번호 1번은 회사의 CEO로 고정되어 있으며, CEO는 항상 팀장이고 팀원일 수 없어 화살표를 받는 쪽이 될 수 없습니다.
3-3. 반면에 CEO를 제외한 나머지 모든 직원들은 다른 누군가로부터 정확히 1개의 화살표를 받게 됩니다.
3-4. 한 직원은 최대 2개의 팀에 소속될 수 있습니다. 만약 어떤 직원이 두 개의 팀에 소속되어 있다면, 반드시 하나의 팀에서는 팀장, 나머지 팀에서는 팀원이어야 합니다. 팀장을 겸임하거나, 두 개의 팀에서 팀원이 될 수는 없습니다. 예를들어 10번 직원은 D팀의 팀장이면서 동시에 5번 직원이 팀장으로 있는 C팀에 속한 팀원입니다
(기타 세부사항은 링크를 참조해주세요)
"제이지"는 자신이 구상한 새로운 사업 아이템에 대해 직원들에게 설명하고자 하루 일정으로 워크숍을 계획하고 있습니다. 단, 모든 직원을 참석시킬 수 없어 아래와 같은 기준으로 워크숍에 참석할 직원들을 선발하려고 합니다.
1. 워크숍에서 교육받은 내용은 전 직원들에게 공유되어야 하므로모든 팀은 최소 1명 이상의 직원을 워크숍에 참석시켜야 합니다.
2. 워크숍 기간 동안, 회사의 매출 손실을 최소화하는 것이 중요하므로 워크숍에 참석하는 직원들의 하루평균 매출액의 합이 최소가 되어야 합니다.
위 그림의 조직도에서 회색으로 색칠된 1번, 7번, 10번 직원을 워크숍에 참석시키면 모든 팀에서 최소 한 명 이상의 직원을 참석시킨 것이 되며, 해당 직원들의 하루평균 매출액의 합은44(14+13+17)원입니다. 10번 직원은 C팀과 D팀 모두에 속해 있으므로, 두 팀에서 모두 참석한 것으로 인정됩니다.
직원들의 하루평균 매출액 값을 담은 배열 sales, 직원들의 팀장-팀원의 관계를 나타내는 2차원 배열 links가 매개변수로 주어집니다. 이때, 모든 팀에서 최소 한 명 이상 워크숍에 참석하면서, 참석하는 직원들의 하루평균 매출액의 합을 최소로 하려고 합니다. 그렇게 최소화된 매출액의 합을 구해서 return 하도록 solution 함수를 완성해 주세요.
DP 문제. 한 서브트리에서 팀장(루트 노드)과 팀원(자식 노드)들의 참여하였을 때의 매출 합계를 DP[node][i]라 하자. i == 0이면 이 노드는 참여하지 않는 것이고, i == 1 이면 이 노드는 참여하는 것이다. 모든 DP 내 node값의 초기값은 [0, sales[node]]가 될 것이다. 이제 이를 팀장의 입장에서 생각해 보자.
i == 1 : 팀장은 무조건 참여하는 게 확정이므로, 이미 전제조건인 최소 참여 인원은 확정되었다. 따라서 각 자식 DP값의 최솟값의 합을 더해 주면 된다.
i == 0 : 팀장이 참여하지 않는 경우이다. 앞선 i == 1인 케이스와 같이 최솟값의 합을 구해 주자.
그런데, 모든 리프값의 최솟값이 자식 노드가 참여하지 않을 때 (DP[leaf][0])가 될 때가 있다. 이 경우는 팀장을 포함한 모든 구성원이 참여하지 않는 셈이므로 조건을 만족할 수 없다. 따라서 자식 노드 중 한 명이 참여해야 한다.
이에 따라 i == 0을 구할 때는, 최솟값과 최댓값의 차가 가장 작은 리프를 저장해야 한다. 이 리프를 저장함으로써 두 번째 최솟값을 저장하는 효과를 가질 수 있다. 만약 각 자식 DP값의 최솟값이 모두 참여하지 않을 때라면, 앞서 저장한 리프 노드를 이용해 최솟값을 최댓값으로 교체한다.
이 규칙에 따라 DP값을 DFS로 구하면, 모든 서브트리에 대한 최적해 및 전체 트리의 최적해를 구할 수 있다.
init : links를 edge_dict으로 변환한다. edge_dict는 어떤 서브트리의 루트 노드를 키값으로, 그리고 자식 노드 리스트를 value값으로 가진다.
dfs : 전체 트리를 재귀적으로 탐색한 다음, 위의 묘사한 조건에 따라 DP값을 업데이트한다. 주의할 점은, 평균 매출값 sales[node]가 0일 때가 존재한다. 즉 이 경우는 DP[node][0] == DP[node][1]인 예외상황이 발생할 수 있으므로, 확실히 DP[node][0] < DP[node][1]일 때만 체크하도록 한다.
solution : 메인함수. init으로 생성되는 edge_dict를 이용하여 dfs를 수행한 후, 루트 노드의 DP값 DP[1]의 최솟값을 반환한다.
풀이 코드
from collections import defaultdict
def init(links) :
edge_dict = defaultdict(list)
for a, b in links :
edge_dict[a].append(b)
return edge_dict
def dfs(node, edge_dict, dp) :
if not edge_dict[node] :
return
cnt, zero_cnt, min_val, min_diff = 0, 0, 0, float('inf')
for leaf in edge_dict[node] :
dfs(leaf, edge_dict, dp)
min_val += min(dp[leaf])
cnt += 1
if dp[leaf][0] < dp[leaf][1] :
zero_cnt += 1
min_diff = min(min_diff, dp[leaf][1] - dp[leaf][0])
dp[node][1] += min_val
dp[node][0] += min_val + min_diff if cnt == zero_cnt else min_val
def solution(sales, links):
dp = [[0,0]] + [[0, sale] for sale in sales]
edge_dict = init(links)
dfs(1, edge_dict, dp)
return min(dp[1])
