[프로그래머스] 매출 하락 최소화 / 2021 KAKAO BLIND RECRUITMENT - JAVA

🖇️ 문제 링크

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

유통전문회사 카카오상사의 오너인 제이지는 새로운 사업 아이템을 구상하기 위해 전문경영인(CEO)인 프로도에게 회사의 경영을 부탁하였습니다. "카카오상사"는 직원들을 여러 개의 팀 단위로 조직을 구성하고 있으며 아래 그림은 CEO를 포함하여 10명의 직원과 4개의 팀으로 구성되어 있는 회사 조직도를 보여주고 있습니다. 그림의 조직도는 다음과 같이 설명할 수 있습니다.

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

 

---

⌨️ 코드

import java.util.*;

class Solution {
    int[] Sales;
    int[][] cost = new int[300000][2];
    List<Integer>[] adj;
    
    public int solution(int[] sales, int[][] links) {
        Sales = sales;
        adj = new ArrayList[Sales.length];
        
        for(int i = 0; i < Sales.length; i++)
            adj[i] = new ArrayList<>();
        
        for(int[] link : links)
            adj[link[0] - 1].add(link[1] - 1);
        
        dfs(0);
        return Math.min(cost[0][0], cost[0][1]);
    }
    
    public void dfs(int idx) {
       	cost[idx][0] = 0;
        cost[idx][1] = Sales[idx];
        
        if(adj[idx].isEmpty())
            return;
        
        int extra = (int)1e9;
        for(int child : adj[idx]) {
            dfs(child);
            if(cost[child][0] < cost[child][1]) {
                cost[idx][0] += cost[child][0];
                cost[idx][1] += cost[child][0];
                extra = Math.min(extra, cost[child][1] - cost[child][0]);
            } else {
                cost[idx][0] += cost[child][1];
                cost[idx][1] += cost[child][1];
                extra = 0;
            }
        }
        
        cost[idx][0] += extra;
    }
}

 

 

 

 

Uploaded by Notion2Tistory v1.1.0