[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/625Reference
この問題について([2021 KAKAO BLIND RECRUITMENT]収入を最大限に下げる), 我々は、より多くの情報をここで見つけました https://velog.io/@titu/2021-KAKAO-BLIND-RECRUITMENT-매출-하락-최소화テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol