#7 매출 하락 최소화
2021 카카오 블라인드
난이도 : LEVEL 4
유형 : 트리 순회 / DP
[문제]
직원들의 하루평균 매출액 값을 담은 배열 sales, 직원들의 팀장-팀원의 관계를 나타내는 2차원 배열 links가 매개변수로 주어집니다. 이때, 모든 팀에서 최소 한 명 이상 워크숍에 참석하면서, 참석하는 직원들의 하루평균 매출액의 합을 최소로 하려고 합니다. 그렇게 최소화된 매출액의 합을 구해서 return 하도록 solution 함수를 완성해 주세요.
[제한사항]
- sales 배열의 크기는 2 이상 300,000 이하입니다. sales 배열의 크기는 CEO를 포함한 전체 직원 수와 같습니다.
- sales 배열은 각 직원들의 하루평균 매출액을 담고 있으며, 1번 직원부터 직원번호 순서대로 주어집니다.
- sales 배열의 각 원소의 값은 0 이상 10,000 이하인 정수입니다.
- links 배열의 크기는 sales 배열의 크기 - 1 입니다. 즉, 전체 직원 수보다 1이 작습니다.
- links 배열의 각 원소는 [a, b] 형식입니다.
- a는 팀장의 직원번호, b는 a팀장이 관리하는 팀원의 직원번호이며, a와 b는 서로 다른 자연수입니다.
- 1 ≤ a ≤ sales 배열의 크기 입니다.
- 2 ≤ b ≤ sales 배열의 크기 입니다.
- 직원번호 1은 CEO로 정해져 있고 CEO는 항상 팀장으므로 b ≠ 1 입니다.
- links 배열로 만들어지는 조직도는 하나의 트리 구조 형태입니다.
- 정답으로 return 되는 값은 2^31 - 1 이하인 자연수임이 보장됩니다.
문제 풀이
트리 구조를 탐색하여 최솟값을 구하는 문제이다. 트리 순회에 대한 개념이 부족한 상태로 크루스칼을 써서 돌려야하는지 DFS로 모든 노드를 시작으로 다 돌려봐야하는지 고민을 많이 하다가 결국 해설을 참고했다.
문제를 천천히 곱씹어보자.
sales 배열의 크기(이하 size)는 2 이상 300,000이다. 이 회사의 구성원은 최대 2명부터 30만명으로 되어있다.
노드 1은 항상 CEO이어서 팀원이 아닌 팀장에만 속한다. 한마디로 루트노드이다.
팀은 팀장 1명과 팀원 n (1 ≤ a ≤ sales-1)으로 이루어져있다.
구상
1) 워크숍에서 참석하는 경우의 수를 무식하게 다 구해보면 총 4가지이다. (감이 안잡힐 때는 일단 천천히 뜯어보는게 최고다)
1. 팀장 o - 팀원 o
2. 팀장 x - 팀원 o
3. 팀장 o - 팀원 x
4. 팀장 x - 팀원 x
4가지의 경우 중 문제가 되는 부분은 4번. 팀장 x- 팀원 x이다. 팀에서 최소 1명은 워크숍에 참석해야하기 때문에 이 부분은 예외처리가 필요해 보인다.
2) 4번. 팀장 x- 팀원 x
만약 한 팀에서 굳이 한 명을 워크숍에 참석해야하는 경우라면 팀에서 최소의 매출을 찍는 팀원을 보내는 것이 팀에 제일 효율적이다.
3) 이러한 과정을 동적 계획법을 사용하여 참석한 경우와 안한 경우의 값을 저장해준다.
cost[1][0] : 1번이 참석하지 않을 경우 cost
cost[1][1] : 1번이 참석할 경우 cost
시뮬레이션
아래의 트리로 시뮬레이션을 한 번 돌려보자.
☛ 노드 1 순회 시작
----cost[1][0] = 0
----cost[1][1] = 5
----A싸이클 (부모 1)> 자식 : 2, 4 탐색
--------------------cost[2][0] = 0
--------------------cost[2][1] = 6
--------------------B싸이클(부모 2) > 자식 : 5, 3 탐색
-------------------------------------cost[5][0] = 0
-------------------------------------cost[5][1] = 4
-------------------------------------cost[3][0] = 0
-------------------------------------cost[3][1] = 5
--------------------B싸이클 종료
--------------------cost[4][0] = 0
--------------------cost[4][1] = 3
----A싸이클 종료
트리를 순회하여 각 노드가 참석할 경우, 안할 경우의 cost를 저장해준다.
여기서 부모 노드를 하나의 싸이클의 기점(A, B)으로 보자 이 하나의 싸이클을 하나의 팀이라고 보면 된다.
이 싸이클 안에서 해야할 과제는 이 4가지의 경우를 모두 조사해서 값을 매긴 다음 cost[부모][]에 Bottom-up방식으로 저장해주면된다. 적은 비용을 구하는 것이 목적이므로 (팀원이 참석할 경우 , 참석 안할 경우) 중 최소의 값을 선택해서 팀장에게 전해주면 된다.
1) cost[자식][0] < cost[자식][1] ▸ 팀원x : 해당 팀원(child)이 참여 안하는게 더 적은 비용이 드는 경우
- 팀장 o - 팀원 x : cost[부모][1] += cost[자식][0]
- 팀장 x - 팀원 x : cost[부모][0] += cost[자식][0]
- 이 로직 안에서 해야할 것이 있다. 2번 팀장x-팀원x 이므로 이 경우를 대비해 팀원의 최소 매출 비용을 구해야한다.
- extra_cost = Math.min(extra_cost, cost[자식][1] - cost[자식][0]);
* cost[자식][0]를 빼는 이유는 cost[부모][0] += cost[자식][0]에서 먼저 더해줬기 때문
2) cost[자식][0] >= cost[자식][1] ▸ 팀원 o 해당 팀원(child)이 참여하는게 더 적은 비용이 드는 경우
- 팀장 o - 팀원 o : cost[부모][1] += cost[자식][1]
- 팀장 x - 팀원 o : cost[부모][0] += cost[자식][1]
이제 그 싸이클을 자세히 뜯어보자. Bottom-up이기 때문에 제일 하위 문제인 B싸이클부터 탐색해보자.
B 싸이클 (부모 노드 2)
☛ 자식 3 탐색
1) cost[3][0] = 0 < cost[3][1] =5
- 팀장 o - 팀원 x : cost[2][1] += cost[3][0] => 6 + 0 = 6
- 팀장 x - 팀원 x : cost[2][0] += cost[3][0] => 0 +0 = 0
- extra_cost = 5-0 =5
☛ 자식 5 탐색
1) cost[5][0] = 0 < cost[5][1] =4
- 팀장 o - 팀원 x : cost[2][1] += cost[5][0] => 6 + 0 = 6
- 팀장 x - 팀원 x : cost[2][0] += cost[5][0] => 0 +0 = 0
- extra_cost = 4 < 5 = 4
B 싸이클 종료
싸이클 종료와 함께 extra_cost값을 저장해준다.
> extra_cost =4 이므로, 아무도 참석 안할 경우 자식 5가 참석을 해야 최소의 매출 하락을 낼 수 있다.
cost[2][0] += extra_cost => 0+4 = 4
cost[2][1] = 6
이제 거슬러서 A싸이클을 탐색해보자.
A 싸이클 (부모 노드 1)
☛ 자식 2 탐색
1) cost[2][0] = 4 < cost[2][1] =6
- 팀장 o - 팀원 x : cost[1][1] += cost[2][0] => 5 + 4 = 9
- 팀장 x - 팀원 x : cost[1][0] += cost[2][0] => 0 +4 = 4
- extra_cost = cost[2][1] - cost[2][0] = 2
☛ 자식 4 탐색
1) cost[4][0] = 0 < cost[4][1] = 3
- 팀장 o - 팀원 x : cost[1][1] += cost[4][0] => 9 + 0 = 9
- 팀장 x - 팀원 x : cost[1][0] += cost[4][0] => 4 +0 = 4
- extra_cost = 2 < 3 = 2
A 싸이클 종료
> extra_cost =4 이므로, 아무도 참석 안할 경우 자식 2가 참석을 해야 최소의 매출 하락을 낼 수 있다.
cost[1][0] += extra_cost => 4+2 = 6
cost[1][1] = 9
모든 싸이클을 돌렸으니 이제 CEO가 참석할 경우 vs CEO가 참석하지 않을 경우 중 작은 값을 구해서 최소 매출 하락을 고르면 된다.
cost[1][0] = 6 < cost[1][1] = 9
따라서, 답은 6이다.
풀이 코드
그림이 잘 안그려질 경우에는 일단 작은 케이스를 만들어서 무식하게 모든 과정을 답사한 다음에 한 싸이클의 그림을 이해하는 방식으로 다가가야겠다.
// blind #7 매출하락최소화 - 트리 순회, DP
import java.util.*;
public class MinimizeSalesDecline {
static int[][] cost;
static int[] extra;
static List<Integer>[] sales_info;
static int[] g_sales;
static int INF = Integer.MAX_VALUE;
public static int solution(int[] sales, int[][] links) {
int answer = INF;
// ====== 초기 설정=======
int n1 = sales.length;
int n2 = links.length;
cost = new int[n1+1][2];
extra = new int[n1+1];
sales_info = new ArrayList[n1+1];
g_sales = new int[n1];
for(int i=0; i<n1; i++ ) {
g_sales[i] = sales[i];
}
for(int i=0; i<n1+1; i++) {
sales_info[i] = new ArrayList<>();
}
for(int i=0; i<n2; i++) {
sales_info[links[i][0]].add(links[i][1]);
}
// =========================
//CEO 1을 기준으로 모든 노드 순회
trevarsal(1);
// 1번 팀장이 참여한 경우 vs 참여하지않은 경우
return Math.min(cost[1][0], cost[1][1]);
}
// 노드 순회 (후위)
static void trevarsal(int pos) {
int child_num = sales_info[pos].size();
cost[pos][0] = 0; // 참석 x
cost[pos][1] = g_sales[pos-1]; // 참석 o
// leaf 노드 도착하면 값만 넣고 return (only 팀원 not 팀장)
if(child_num ==0 )return;
int extra_cost = INF;
// ============== 싸이클 시작 ================
// 부모 -> 자식 탐색
for(int child : sales_info[pos]) {
trevarsal(child); // child 탐색
// ex) parent1 -> (4,2) 탐색 후 아래 로직 실행
// 팀원x : 해당 팀원(child)이 참여 안하는게 더 적은 비용이 드는 경우
if(cost[child][0] < cost[child][1]) {
cost[pos][0] += cost[child][0]; // 팀장 x 팀원 x -> 예외처리 필요(다른 자식노드 참여)
cost[pos][1] += cost[child][0]; // 팀장 o 팀원 x
// 팀장x 팀원x인 경우 한 팀에 최소 한명이니깐 팀원 중 최소비용 추가해놓기
extra_cost = Math.min(extra_cost, cost[child][1] - cost[child][0]);
}
// 팀원 o : 해당 팀원(child)이 참여하는게 더 적은 비용이 드는 경우
else {
cost[pos][0] += cost[child][1]; // 팀장 x 팀원 o
cost[pos][1] += cost[child][1]; // 팀장 o 팀원 o
// 팀장x 팀원o 이면 다른 자식이 참여헀으니깐 0으로 초기화
extra_cost = 0;
}
}
// ============== 싸이클 종료 ================
// System.out.println(pos +" 팀장 참여안할 때 최소비용드는 팀원 cost: " + extra_cost);
cost[pos][0] += extra_cost; // 아무도 참석 안할 경우 최소비용 팀원 추가
}
// 메인 함수
public static void main(String[] args) {
// int[] sales = {14, 17, 15, 18, 19, 14, 13, 16, 28, 17};
// int[][] links = { {10, 8}, {1, 9}, {9, 7},
// {5, 4}, {1, 5}, {5, 10}, {10, 6},
// {1, 3}, {10, 2} };
int[] sales = {5,6,5,3,4};
int[][] links = { {2,3}, {1,4}, {2,5}, {1,2} };
System.out.println(solution(sales, links));
}
}
'Dot Algo∙ DS > PS' 카테고리의 다른 글
[BOJ] 백준 16916번 부분 문자열 KMP (Java) (0) | 2021.05.11 |
---|---|
[BOJ] 백준 1389번 케빈 베이컨의 6단계 법칙 (Java) (0) | 2021.05.09 |
[BOJ] 백준 12015번 가장 긴 증가하는 부분 수열2 LIS - 이진탐색 (Java) (0) | 2021.05.05 |
[BOJ] 백준 11053번 LIS 가장 긴 증가하는 부분 수열 LIS - DP(Java) (0) | 2021.05.05 |
[BOJ] 백준 13711번 LCS4 (Java) (0) | 2021.05.04 |