매출 하락 최소화

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

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

 

현재까지 카카오 기출을 풀어오면서 처음으로 종이와 펜을 꺼냈다..

 

해결 방법 : DFS 완전탐색 + DP 응용

• DFS의 Postorder 방법으로 하위팀 → 상위팀 으로 탐색한다.
• 하위팀부터 팀장의 [참석시 최소비용, 불참시 최비용]을 구한다.
  • 특정 팀장의 참석시 최소비용
    • 팀장 비용 + sum(하위팀의  최소비용)
  • 특정 팀장의 불참시 최소비용
    • 하위팀 중 1팀이라도 팀장이 참석하는게 해당 팀의 최소비용이면,
      • sum(하위팀의 최소비용)
    • 모든 하위팀의 최소비용이 팀장이 불참하는 경우라면,
      
      • min(현재팀 일반 팀원 최소비용, 하위팀 중 한 곳의 팀장이 참석함으로써 생기는 최소의 추가비용)에 따라 결정된다.
• 이와 같이 Postorder로 탐색하여 CEO(1번 직원)에 대한 [참석시 최소비용, 불참시 최소비용]이 구해지고, 둘 중 작은 값을 반환한다.

 

from collections import defaultdict

def solution(sales, links):

    s_dict = {i + 1 : s for i, s in enumerate(sales)} # {모든 직원 : 매출}
    T = defaultdict(list) # 회사 조직도 트리
    C = dict() # {매니저 : [참석시 비용, 불참시 비용]}

    for p, c in links: # 트리 구성
        T[p].append(c)

    def dfs(node): # DFS
        if T.get(node) is None: # 일반 팀원이면 return
            return
		### CEO or 매니저 ###
        attcost, abscost = s_dict[node], 0 # 참석시 비용, 불참시 비용 
        managerAtt = False # 현재팀 팀원들 중에서 매니저가 참석하는지 판단
        mincostOfemp = mingapOfmanager = float('inf') # 팀원 최소비용, 매니저가 참석하는데의 추가 비용

        for c in T[node]: # 모든 팀원 탐색
            dfs(c)

            if C.get(c) is None: # 일반 팀원
                mincostOfemp = min(mincostOfemp, s_dict[c]) # 최소 비용

            else: # 매니저
                attcost += min(C[c]) 
                abscost += min(C[c])
                if min(C[c]) == C[c][0]: # 매니저 참석이 최소 비용인 경우
                    managerAtt = True 
                else: # 각 매니저가 참석할시, 추가 비용의 최소값
                    mingapOfmanager = min(mingapOfmanager, C[c][0] - C[c][1])

        if managerAtt == False: # 모든 매니저 불참시
        # min(최소비용 직원 참석, 추가비용이 최소인 매니저가 참석)
            abscost += min(mincostOfemp, mingapOfmanager)

        C[node] = [attcost, abscost]

    dfs(1)

    return min(C[1])