[2021 KAKAO BLIND RECRUITMENT] 매출 하락 최소화

2021 KAKAO 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