[2021 KAKAO BLIND RECRUITMENT]収入を最大限に下げる


2021 KAO BLIND RECRUITMENT販売下落最小化

を選択します。

  • DFS
  • ツリー
  • 問題を解く感覚をつかむために、まずココ公式問題解説を参考にしました.

    コード#コード#

    import java.util.ArrayList;
    import java.util.List;
    import java.util.stream.IntStream;
    
    class Solution {
        class Team {
            int leader;
            int sale;
            List<Integer> followers = new ArrayList<>();
    
            public Team(int leader, int sale) {
                this.leader = leader;
                this.sale = sale;
            }
        }
    
        static List<Team> teams = new ArrayList<>();
        static int[][] dp;
    
        public int solution(int[] sales, int[][] links) {
            // 직원들의 하루평균 매출액 값을 담은 배열 sales, 직원들의 팀장-팀원의 관계를 나타내는 2차원 배열 links
    
            // 모든 팀에서 최소 한 명 이상 워크숍에 참석하면서, 참석하는 직원들의 하루평균 매출액의 합의 최솟값
            int answer = 0;
    
            teams.add(null);
            IntStream.range(1, sales.length + 1).forEach(i -> teams.add(new Team(i, sales[i-1])));
    
            for (int[] link : links) {
                int leader = link[0];
                int follower = link[1];
    
                teams.get(leader).followers.add(follower);
            }
    
            dp = new int[sales.length + 1][2];
            // 1.
            // dp[i][1]은 i번 직원이 워크숍에 참석했을 경우, (워크숍에 참석하는 직원들의 하루평균 매출액의 합의) 최솟값
            // dp[i][0]은 i번 직원이 워크숍에 참석하지 않았을 경우, (워크숍에 참석하는 직원들의 하루평균 매출액의 합의) 최솟값
    
            // 2.
            // /* i번 직원이 워크숍에 참석했을 경우 */
            // -> i번 직원이 속한 팀에서, i번 직원이 참가하기 때문에 팀원들이 참가하는지 여부는 중요 X
            // dp[i][1] = sales[i] + sumOfChild
            // sumOfChild = sum(min(dp[j][0], dp[j][1]))
            // EX)
            // dp[i][1]의 값은 i번 직원을 팀장으로 하는 팀원 j1, j2가 있다고 했을 때
            // sumOfChild = min(dp[j1][0], d[j1][1]) + min(dp[j2][0], dp[j2][1])
    
            // /* i번 직원이 워크숍에 참석하지 않았을 경우 */
            // -> i번 직원이 속한 팀에서, i번 직원이 참가하지 않기 때문에, 팀원들 중 최소 한 명이 참가해야 함
            // 만약 sumOfChild를 계산하는 과정에서,
            // 1) 한 번이라도 팀원이 (불참하는 경우 > 참석하는 경우)여서 dp[j][0] > dp[j][1]여서, 최소 한 명의 팀원이 참석하는 경우
            // dp[i][0] = sumOfChild
            // 2) 모든 경우에 팀원이 (참석하는 경우 > 불참하는 경우)여서 dp[j][1] > dp[j][0]여서, 팀원이 한 명도 참석하지 않는 경우
            // dp[i][0] = sumOfChild + min(dp[j][1] - dp[j][0])
            // min(dp[j][1] - dp[j][0]): 팀원 중 한 명이 불참했다가 참석할 경우에 추가되는 손해값의 최솟값
            // EX)
            // dp[i][0]의 값은 i번 직원을 팀장으로 하는 팀원 j1, j2가 있다고 했을 때
            // sumOfChild = min(dp[j1][0], d[j1][1]) + min(dp[j2][0], dp[j2][1])
            // sumOfChild를 계산하는 과정에서, dp[j1][1] > dp[j1][0], dp[j2][1] > dp[j2][0]여서
            // sumOfChild = dp[j1][0] + dp[j2][0]인 경우,
            // dp[j1][1] - dp[j1][0]와 dp[j2][1] - dp[j2][0]중 더 작은 값을 찾아 더해줘야 한다.
            // 만약 dp[j1][1] - dp[j1][0]이 더 작은 값이라면, j1 팀원이 참석하는 경우가 가장 손해가 적을 것이고,
            // 이 경우, dp[i][0] = sumOfChild + dp[j1][1] - dp[j1][0]이 된다.
            // dp[i][0] = dp[j1][0] + dp[j2][0] + dp[j1][1] - dp[j1][0] = d[j1][1] + dp[j2][0]
    
            // 3.
            // CEO는 1번 직원이며, 최상단의 팀장이므로 트리 안에서의 루트 노드다.
            // 우리가 구하고자 하는 값은 min(dp[1][0], dp[1][1])이다.
    
            // 4.
            // 루트노드부터 리프노드까지 순회하며 dp값을 채워준다.
            DFS(1);
            answer = Math.min(dp[1][0], dp[1][1]);
    
            return answer;
        }
    
        private void DFS(int leader) {
            boolean noOneAttend = true;
            int minOfDifference = 10001;
            int sumOfChild = 0;
    
            for (Integer follower : teams.get(leader).followers) {
                DFS(follower);
                int difference = dp[follower][1] - dp[follower][0];
                if (difference < 0) noOneAttend = false;
                else {
                    if (difference < minOfDifference) minOfDifference = difference;
                }
                sumOfChild += Math.min(dp[follower][0], dp[follower][1]);
            }
    
            int sale = teams.get(leader).sale;
            dp[leader][1] = sale + sumOfChild;
    
            int numOfFollowers = teams.get(leader).followers.size();
            if(numOfFollowers == 0) dp[leader][0] = 0;
            else {
                if(noOneAttend) dp[leader][0] = sumOfChild + minOfDifference;
                else dp[leader][0] = sumOfChild;
            }
        }
    }
    注意:https://yabmoons.tistory.com/625