프로그래머스: 매출 하락 최소화⭐⭐⭐⭐
카테고리: Programmers
태그: Algorithm, Blog, C++, Programmers
난이도 ⭐⭐⭐⭐
유형 : 탐색, 자료구조
🧐 문제
문제 설명
유통전문회사 카카오상사의 오너인 제이지는 새로운 사업 아이템을 구상하기 위해 전문경영인(CEO)인 프로도에게 회사의 경영을 부탁하였습니다.
“카카오상사”는 직원들을 여러 개의 팀 단위로 조직을 구성하고 있으며 아래 그림은 CEO를 포함하여 10명의 직원과 4개의 팀으로 구성되어 있는 회사 조직도를 보여주고 있습니다.
그림의 조직도는 다음과 같이 설명할 수 있습니다.
- 그림의 각 원들은 각각의 직원 1명을 표시하고 있으며, CEO를 포함하여 총 10명의 직원을 표시하고 있습니다.
-
원 안에 적힌 두 개의 숫자는 직원의 정보를 담고 있습니다. 왼쪽 숫자는
직원번호이며 직원을 식별할 수 있도록 1번부터 순서대로 발급되는 일련번호이며, 오른쪽 숫자는해당 직원의 하루평균 매출액을 나타냅니다. 위 그림에서1번직원은 14원을,9번직원은 28원의 하루평균 매출액을 기록하고 있습니다. - CEO를 포함하여 모든 직원은 팀장 또는 팀원이라는 직위를 가지고 있으며 그림에서는 팀장과 팀원의 관계를 화살표로 표시하고 있습니다. 화살표가 시작되는 쪽의 직원은 팀장, 화살표를 받는 쪽의 직원은 팀원을 의미합니다.
3-1. 직원번호1번은 회사의 CEO로 고정되어 있으며, CEO는 항상 팀장이고 팀원일 수 없어 화살표를 받는 쪽이 될 수 없습니다.
3-2. 반면에 CEO를 제외한 나머지 모든 직원들은 다른 누군가로부터 정확히 1개의 화살표를 받게 됩니다.
3-3. 한 직원은 최대 2개의 팀에 소속될 수 있습니다. 만약 어떤 직원이 두 개의 팀에 소속되어 있다면, 반드시 하나의 팀에서는 팀장, 나머지 팀에서는 팀원이어야 합니다. 팀장을 겸임하거나, 두 개의 팀에서 팀원이 될 수는 없습니다. 예를들어10번직원은D팀의 팀장이면서 동시에5번직원이 팀장으로 있는C팀에 속한 팀원입니다.
3-4.5번, 9번, 10번직원은 받는 쪽의 화살표와 시작하는 화살표가 모두 있으므로 팀장인 동시에 팀원입니다.
3-5.2번, 3번, 4번, 6번, 7번, 8번직원은 시작하는 화살표가 없고 받는 쪽의 화살표만 있으므로 팀장이 아니며 오직 팀원입니다.
3-6.1번직원인 CEO는 받는 쪽의 화살표가 없고 시작하는 화살표만 있으며 항상 팀원이 아닌 팀장입니다.
3-7. 그림의 조직도에는A, B, C, D총 4개의 팀이 존재하며, 각각1번, 9번, 5번, 10번직원이 팀장 직위를 담당하게 됩니다.
“제이지”는 자신이 구상한 새로운 사업 아이템에 대해 직원들에게 설명하고자 하루 일정으로 워크숍을 계획하고 있습니다. 단, 모든 직원을 참석시킬 수 없어 아래와 같은 기준으로 워크숍에 참석할 직원들을 선발하려고 합니다.
- 워크숍에서 교육받은 내용은 전 직원들에게 공유되어야 하므로
모든 팀은 최소 1명 이상의 직원을 워크숍에 참석시켜야 합니다. - 워크숍 기간 동안, 회사의 매출 손실을 최소화하는 것이 중요하므로 워크숍에 참석하는 직원들의 하루평균 매출액의 합이 최소가 되어야 합니다.
위 그림의 조직도에서 회색으로 색칠된 1번, 7번, 10번 직원을 워크숍에 참석시키면 모든 팀에서 최소 한 명 이상의 직원을 참석시킨 것이 되며, 해당 직원들의 하루평균 매출액의 합은 44(14+13+17)원 입니다. 10번 직원은 C팀과 D팀 모두에 속해 있으므로, 두 팀에서 모두 참석한 것으로 인정됩니다.
[문제]
직원들의 하루평균 매출액 값을 담은 배열 sales, 직원들의 팀장-팀원의 관계를 나타내는 2차원 배열 links가 매개변수로 주어집니다. 이때, 모든 팀에서 최소 한 명 이상 워크숍에 참석하면서, 참석하는 직원들의 하루평균 매출액의 합을 최소로 하려고 합니다. 그렇게 최소화된 매출액의 합을 구해서 return 하도록 solution 함수를 완성해 주세요.
[제한사항]
- sales 배열의 크기는 2 이상 300,000 이하입니다. sales 배열의 크기는 CEO를 포함한 전체 직원 수와 같습니다.
- sales 배열은 각 직원들의 하루평균 매출액을 담고 있으며,
1번직원부터 직원번호 순서대로 주어집니다. - sales 배열의 각 원소의 값은 0 이상 10,000 이하인 정수입니다.
- sales 배열은 각 직원들의 하루평균 매출액을 담고 있으며,
- 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 되는 값은 231 - 1 이하인 자연수임이 보장됩니다.
[입출력 예]
| sales | links | result |
|---|---|---|
| [14, 17, 15, 18, 19, 14, 13, 16, 28, 17] | [[10, 8], [1, 9], [9, 7], [5, 4], [1, 5], [5, 10], [10, 6], [1, 3], [10, 2]] | 44 |
| [5, 6, 5, 3, 4] | [[2,3], [1,4], [2,5], [1,2]] | 6 |
| [5, 6, 5, 1, 4] | [[2,3], [1,4], [2,5], [1,2]] | 5 |
| [10, 10, 1, 1] | [[3,2], [4,3], [1,4]] | 2 |
입출력 예 설명
접기/펼치기
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
직원번호가 2인 직원 한 명을 워크숍에 참석시키는 것이 최선이며, 2번 직원의 하루평균 매출액은 6원입니다. 따라서 6을 return 해주어야 합니다.
입출력 예 #3
직원번호가 4, 5인 직원 두 명을 워크숍에 참석시키는 것이 최선이며, 4번, 5번 직원의 하루평균 매출액의 합은 5(1+4)원 입니다. 따라서 5를 return 해주어야 합니다.
입출력 예 #4
직원번호가 3, 4인 직원 두 명을 워크숍에 참석시키는 것이 최선이며, 3번, 4번 직원의 하루평균 매출액의 합은 2(1+1)원 입니다. 따라서 2를 return 해주어야 합니다.
🔍 힌트
이 문제는 트리 DP문제이다.
트리DP를 사용하지 못하면 해결하기 매우 힘든 문제다.
접근 방법은 다음과 같다.
- DFS로 트리 탐색
- 트리의 루트 노드에서 시작하여 모든 노드를 탐색한다.
- DFS를 통해 리프 노드까지 내려갔다가, 거슬러 올라오며 DP 값을 채워나간다.
- DP 배열
- DP 배열은 ‘dp[노드 개수][2]로 정의한다.
- ‘dp[i][0]’ : 현재 노드 ‘i’가 워크샵에 참석하지 않을 때, 하위 노드들을 포함한 최소 비용
- ‘dp[i][1]’ : 현재 노드 ‘i’가 워크샵에 참석할 때, 하위 노드들을 포함한 최소 비용
- DP 값 갱신
- 리프 노드의 dp 값은 미리 갱신해둔다.
- 리프 노드가 아닌 노드에서, 하위 노드들의 DP 값을 이용하여 자신의 DP 값을 계산한다.
- DP에서 dp[팀장][0], dp[팀장][1]
이 두개는 무조건 계산해야한다. - 그러므로 아래와 같이
‘팀장 참석O’,
‘팀장 참석X, 팀원 참석O’,
‘팀장 참석X, 팀원 참석X’
총 3개로 나눈다.
- 경우의 수
- 팀장 참석O (‘dp[팀장][1]’)
- 팀장이 워크샵에 참석하는 경우, 하위 노드들이 참석하거나 참석하지 않는 경우 중 최소 비용을 더한다. (팀원들의 최소합)
- 즉, dp[팀장][1] = sales[팀장] + sum(min(dp[팀원][0], dp[팀원][1]))이 된다. - 팀장 참석X, 팀원 참석O (‘dp[팀장][0]’)
- 팀원이 한명이라도 참석하게 되는 경우는
‘dp[팀원][0] >= dp[팀원][1]’
과 같이 참석하는 경우가 오히려 최소 비용인 경우이다. - 따라서 위와 같은 상황에 있는 팀원이 ‘한명이라도 있는지’ 확인하면 된다.
- 즉, dp[팀장][0] = sum(min(dp[팀원][0], dp[팀원][1])) 이 될 것이다. - 팀장 참석X, 팀원 참석X (‘dp[팀장][0]’)
- ‘dp[팀원] >= dp[팀원][1]’ 인 사람이 한명도 없는 상황이라면, 팀원중 한명을 강제로 참석시켜야 한다.
- 그러한 상황에선 팀원 중 참석 비용이 제일 적은 한명을 선택해야한다.
- min_gap = min(min_gap, dp[팀원][1]-dp[팀원][0])을 팀원 수 만큼 돌리고,
dp[팀장][0] = sum(min(dp[팀원][0], dp[팀원][1])) + min_gap 를 해주면 된다.
mingap의 의미는 미리 더해주고 dp[팀원][1]-dp[팀원][0]만큼 더해주기 위함이다.
✏️ 나의 풀이
첫번째 시도 (시간 초과)
#include <bits/stdc++.h>
using namespace std;
// 팀마다의 참석 정보
unordered_map<int, bool> attend;
// 각 팀의 노드들
map<int, set<int>> teams;
int result = INT_MAX;
int total = 0;
void dfs(vector<int>& sales) {
// 현재 계산한 최소 비용이 더 크다면 가지치기
if(result < total) return;
// 모든 팀이 참석했는지 확인
for(auto t_iter = teams.begin(); t_iter != teams.end(); t_iter++) {
if(!attend[t_iter->first]) break;
if(t_iter == prev(teams.end())) {
result = min(result, total);
return;
}
}
for(auto t_iter = teams.begin(); t_iter != teams.end(); t_iter++) {
// 루트 노드. 현재 팀 index로 쓰인다.
int key = t_iter->first;
// 아직 참석하지 않은 팀이라면
if(!attend[key]) {
// 해당 팀원들(팀장 포함)
set<int> attend_set = t_iter->second;
for(auto a_iter = attend_set.begin(); a_iter != attend_set.end(); a_iter++) {
// 이미 참석한 팀원이라면 continue
if(attend[*a_iter]) continue;
// 백트래킹
// key : 현재 팀 index
// *a_iter : 팀원의 팀 index
attend[key] = true;
attend[*a_iter] = true;
total += sales[*a_iter-1];
dfs(sales);
attend[key] = false;
attend[*a_iter] = false;
total -= sales[*a_iter-1];
}
}
}
}
void init(vector<int>& sales, vector<vector<int>>& links) {
for(vector<int> link : links) {
int cur_node = link[0];
int next_node = link[1];
teams[cur_node].insert(cur_node);
teams[cur_node].insert(next_node);
attend[cur_node] = false;
}
team_size = teams.size();
}
int solution(vector<int> sales, vector<vector<int>> links) {
int answer = 0;
init(sales, links);
dfs(sales);
return result;
}
처음에 문제를 보았을 때, 어떻게 푸는 것인지 감이 잡히지 않았다.
그래서 생각을 계속 해보다가, 일단은 백트래킹으로 풀어봤다.
실행해 보았을 때 답은 잘 나왔으나, 시간초과으로 문제 해결에 실패했다.
시간복잡도가 $O(2^n * n^2)$ 였으니 당연히 안될만 했다.
두번째 시도
#include <bits/stdc++.h>
using namespace std;
int cost[300001][2];
vector<int> tree[300001];
void dfs(vector<int>& sales, int cur) {
// 리프 노드라면
if(tree[cur].empty()) return;
int sum=0;
int min_cost = INT_MAX; // 아무도 참석을 안하려 할 때를 대비함
bool isAttend = false; // 한명이라도 참석했는가?
vector<int> childs = tree[cur];
for(int i=0; i<childs.size(); i++) {
dfs(sales, childs[i]);
sum += min(cost[childs[i]][0], cost[childs[i]][1]);
if(cost[childs[i]][0] >= cost[childs[i]][1]) isAttend = true;
min_cost = min(min_cost, cost[childs[i]][1] - cost[childs[i]][0]);
}
// 팀장 O
cost[cur][1] = sales[cur-1] + sum;
// 팀장 X, 팀원 O
if(isAttend) {
cost[cur][0] = sum;
}
// 팀장 X, 팀원 X
else {
cost[cur][0] = sum + min_cost;
}
}
void init(vector<int>& sales, vector<vector<int>>& links) {
for(vector<int> link : links) {
int parent = link[0];
int child = link[1];
cost[child][0] = 0;
cost[child][1] = sales[child-1];
tree[parent].push_back(child);
}
}
int solution(vector<int> sales, vector<vector<int>> links) {
int answer = 0;
init(sales, links);
dfs(sales, 1);
return min(cost[1][0], cost[1][1]);
}
✔️ 다른 사람의 풀이
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> adj[300005];
vector<int> s;
ll d[300005][2];
ll INF = 0x7fffffff7fffffff;
void dfs(int cur){
if(adj[cur].empty()){ // leaf일 경우
d[cur][0] = s[cur];
d[cur][1] = 0;
return;
}
ll mingap = INF;
d[cur][0] = s[cur];
for(auto x : adj[cur]){
dfs(x);
// 팀원들의 비용 최소합을 구함.
// 내 코드에선 sum 변수에 해당하는 부분이다.
d[cur][0] += min(d[x][0],d[x][1]);
// 강제로 참석해야하는 경우를 위한 변수이다.
mingap = min(mingap, d[x][0] - d[x][1]);
}
// 참석하는 팀원이 있는 경우, mingap을 0으로 만든다.
if(mingap < 0) mingap = 0;
// '팀장X, 팀원O', '팀장X, 팀원X' 경우 모두 여기서 처리한다.
d[cur][1] = d[cur][0] + mingap - s[cur];
}
int solution(vector<int> sales, vector<vector<int>> links) {
s.push_back(0);
for(auto x : sales) s.push_back(x);
for(auto x : links)
adj[x[0]].push_back(x[1]);
dfs(1);
return min(d[1][0],d[1][1]);
}
🧐 분석
- DFS로 리프노드에 도착하고서야, 해당 DP의 값을 초기화해주고 있다.
- [0]을 참석한 경우, [1]을 참석하지 않은 경우로 계산하고 있다.
- d[cur][1] = d[cur][0] + mingap - s[cur];
해당 코드에서 두가지 경우를 한번에 처리하고 있다.
d[cur][0] 또한 재사용하고 있다.
🪶 후기
이번 문제는 너무 어려워서 다른 사람의 도움을 많이 받았다..
트리DP에 대해 모르는 상태로 이 문제에 도전했다.
백트래킹으로 어떻게든 풀긴했는데… 시간 초과로 망했다.
레벨5 시험장 나누기 문제마냥 도대체 어떻게 하는거지? 하루종일 생각만 하다가 GG쳤다.
결국 다른 사람 풀이를 봐야했고..
이번 기회에 트리DP가 무엇인지 이리저리 맨땅에 헤딩하며 제대로 알게 됐다.
댓글남기기