코드
from collections import defaultdict
def solution(sales, links):
global graph, DP
graph = defaultdict(list)
for v1, v2 in links :
graph[v1-1].append(v2-1)
DP = [[0, 0, 0] for _ in range(len(sales))]
dfs(sales, 0)
return min(DP[0][0], DP[0][1])
def dfs(sales, node) :
if node not in graph :
DP[node][1] = sales[node]
else :
for child in graph[node] :
dfs(sales, child)
children = graph[node]
flag = sum(DP[child][2] for child in children)
DP[node][1] = sales[node] + (s := sum(min(DP[child][0] , DP[child][1]) for child in children))
DP[node][0] = s if flag else s + min(DP[child][1] - DP[child][0] for child in children)
DP[node][2] = 1 if DP[node][1] < DP[node][0] else 0
알고리즘
DFS를 이용해leaf노드부터, 해당노드가 참석할 때, 불참할 때의 최적해를 구해나간다.
팀 정보(DP)
DP는 각 노드가 팀장일 때 해당팀의 정보를 저장한다.
0: 팀장이 참석 안했을 때의 최솟값
1: 팀장이 참석 했을 때의 최솟값
2:1 if 팀장 참석 최솟값 < 팀장 불참 최솟값 else 0
2 같은 경우는 해당노드의 팀장의 DP를 구할때를 위한 정보
DP[팀장][1]
해당 팀에서 팀장이 참석하는 경우의 최소값은
DP[팀장][1] = sales[팀장노드] + sum(min(DP[팀원][0], DP[팀원][1]))
하위 팀원들의 최솟값들과 팀장 본인의 값을 더해주면 된다.
DP[팀장][0]
- case 1 : 팀장이 참석 안하고 모든 팀원이 참석 안함
- case 2 : 팀장이 참석 안하고 팀원 중 최소 1명이 참석
문제는 여기서 생긴다. 팀장포함 팀원 모두가 회의참석해도 상관없지만, 팀내에서 아무도 참석하지 않는 경우는 발생해선 안된다. DP[k][1] 은 팀장이 참석하는 가정하에 팀의 최솟값을 구하는 거였기 때문에 상관없었지만 DP[k][0]은 팀장이 참석안하는 경우다. 따라서 이런 경우가 생길 수 있다.
모든 팀원에 대해, 각 팀원이 참석하지 않았을 때 ‘팀원의 팀’이 최솟값인 경우
팀원팀원 거려서 헷갈릴 수 있는데 쉽게말해 이런경우다.
팀장은 참석 안하기로 했고, 모든 팀원이 본인이 참석하지 않는 경우에 각팀이 최솟값이 된다. 이런경우에는
이렇게 팀원 한명을 DP[팀원][1] 로 바꿔줘야한다(팀원 한명을 참석시킨다). 당연히 한명을 참석시킬 때 값의 변화가 가장 작은 팀원을 참석 시켜주어야 하므로
DP[팀장][0] = sum(min(DP[팀원][0], DP[팀원][1])) + DP[최소팀원][1] - DP[최소팀원][0]
을 해주면 된다.
이런 경우엔 최소 팀원 한명이 팀에서 참석 하므로 팀원들의 최솟값 합을 구해주면된다.
s = sum(min(DP[팀원][0], DP[팀원][1]))
DP[팀장][0] = s if 팀원 중 누군가 참석 else s + DP[최소팀원][1] - DP[최소팀원][0]
이런식으로 코드 작동
from collections import defaultdict
def solution(sales, links):
global graph, DP
graph = defaultdict(list)
for v1, v2 in links :
graph[v1-1].append(v2-1)
DP = [[0, 0, 0] for _ in range(len(sales))]
dfs(sales, 0)
return min(DP[0][0], DP[0][1])
def dfs(sales, node) :
if node not in graph : # leaf 노드인 경우
DP[node][1] = sales[node]
else : # non-leaf 노드인 경우
for child in graph[node] :
dfs(sales, child)
children = graph[node]
flag = sum(DP[child][2] for child in children) # 팀원이 아무도 참석안하면 0, 누군가 참석하면 1 이상
DP[node][1] = sales[node] + (s := sum(min(DP[child][0] , DP[child][1]) for child in children))
DP[node][0] = s if flag else s + min(DP[child][1] - DP[child][0] for child in children)
DP[node][2] = 1 if DP[node][1] < DP[node][0] else 0
테페리넷 코드
"""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)
내생각 가장잘짠 코드 테페리넷, 속도는 살짝 느리지만 가독성이 너무 좋고 이 사람 블로그에가서 코드를 보면 추구하는 코딩스타일이 같다. 물론 실력은 내가 훨씬 아래지만… 이사람 블로그보고 공부 많이 하는 중