[프로그래머스] Lv4. 매출 하락 최소화 (2021 카카오 코테)

🔗

풀이

1. 반드시 한 팀에서 최소 1명 이상 참석해야 한다.
2. 참석한 직원들의 매출액 합이 최소가 되어야 한다.
3. 팀장이 참석한 경우 팀원들은 참석해도 되고, 하지 않아도 됨. 둘 중 최소 값.
4. 팀장이 참석하지 않는다면 반드시 최소 1명의 팀원은 참석해야 함.

1번 직원부터 시작해서 트리 순회를 하면서 팀원들의 참석 여부에 따른 매출액에 따라 팀장의 참석 여부와 매출액을 결정하게 되는 문제이다.

전체 크기가 30만이기 때문에 모든 경우를 따지는 완전 탐색으로는 풀이가 불가능하고 다이나믹 프로그래밍을 사용해 풀이했다.

dp[직원 번호][참석 여부]
0 : 참석
1 : 불참

후위 순회로 모든 팀원 노드들에 대해 탐색하면서 팀원의 참석/불참 매출액 가운데 최소값을 구한다. 팀장이 참석하는 경우에는 팀원의 참석/불참 여부가 중요하지 않으므로 둘 중 최소값만 저장하면 된다. 하지만 팀장이 불참하는 경우는 복잡해진다. 반드시 1명의 팀원은 참석해야 하기 때문이다.

처음에는 강제로 1명의 팀원을 참여시킨다고 가정하고 참여했을 때 매출액이 가장 적은 직원을 고르는 방식을 택했다. 그러나 잘 생각해보면 해당 방식은 좀 문제가 있음을 알 수 있다.

우선 팀장이 불참하고, 모든 팀원이 불참하는 경우를 가정했다. 단 한명의 팀원이라도 참여하게 되는 경우는 include 변수를 참으로 변경해서 해당 연산이 실행되지 않도록 했다. 한 팀에서 한 명은 반드시 참여해야 하고 현재 팀장은 무조건 불참하기로 결정된 상태이므로 1명의 팀원을 골라야 하는데 이때 참여했을 때 값이 최소인 팀원은 최선의 선택이 아니다.

현재 모든 팀원은 불참인 상태이므로 현재 참여시키려고하는 팀원도 불참인 상태다. 이 팀원을 참여시키려면 참여 상태로 변경해야 하는데 우선 기본적으로 불참인 상태가 참여인 상태보다 매출액이 적기 때문에 선택된 것이기 때문에 참여할 때의 매출액이 불참일 때보다 클 수 밖에 없다. 그래서 이 팀원을 참여시킨다는 것은 결국 해당 팀원이 불참일 때의 매출액을 빼고 참여일 때의 매출액을 더한다는 소리가 된다. (해당 팀원의 참여일 때 매출액 - 불참일 때 매출액)의 차이값이 더해지게 되는 셈이다. 결국 이 값이 가장 최소가 되는 팀원을 선택해야 최선의 선택이 된다.

import java.util.*;

class Solution {
    List<List<Integer>> tree;
    int[][] dp;
    public void dfs(int cur, int[] sales) {
        dp[cur][0] += sales[cur];
        if (tree.get(cur).size() == 0) return;
        
        int tmpSum = 0;
        int minGap = Integer.MAX_VALUE;
        boolean include = false;
        for (int child : tree.get(cur)) {
            dfs(child, sales);
            
            dp[cur][0] += Math.min(dp[child][0], dp[child][1]);
            if (dp[child][0] < dp[child][1]) {
                // 이때 팀장(cur)이 참여하지 못하는 경우 팀원 중 한 명은 반드시 참여해야 하는데 
                // 이 경우는 팀원 한 명이 참여했으므로 팀원 참여 여부(include)를 true로 변경
                dp[cur][1] += dp[child][0]; 
                include = true;
            } else {
                dp[cur][1] += dp[child][1];
                // 팀장이 참여하지 못했는데 팀원도 한 명도 참여하지 못했으므로
                // 팀원들 가운데 참여하는 것과 참여하지 못하는 것 사이의 차이(minGap)가 가장 적은 팀원을 
                // 팀장이 참여하지 못한 경우(include = false) 참여시키는 것
                minGap = Math.min(minGap, dp[child][0] - dp[child][1]);
                
            }
        }
        
        if (!include) {
            dp[cur][1] += minGap;
        }
        
    }
        
    public int solution(int[] sales, int[][] links) {
        int N = sales.length;
        
        tree = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            tree.add(new ArrayList<>());
        }
            
        for (int[] link : links) {
            tree.get(link[0]-1).add(link[1]-1);
        }
            
        dp = new int[N][2];
        dfs(0, sales);

        return Math.min(dp[0][0], dp[0][1]);
    }
}