문제 설명: 직원들의 하루평균 매출액 값을 담은 배열 sales, 직원들의 팀장-팀원의 관계를 나타내는 2차원 배열 links가 매개변수로 주어집니다. 이때, 모든 팀에서 최소 한 명 이상 워크숍에 참석하면서, 참석하는 직원들의 하루평균 매출액의 합을 최소로 하려고 합니다. 그렇게 최소화된 매출액의 합을 구해서 반환하는 함수를 작성
두 팀에 속한 1명은 팀장 이면서 팀원 이어야 함 -> 참석하면 두 팀이 참석한 것
CEO는 항상 1번
입력
sales 배열의 크기는 2 이상 300,000 이하
sales 배열의 크기는 CEO를 포함한 전체 직원 수
sales 배열의 각 원소의 값은 0 이상 10,000 이하인 정수
links 배열의 크기는 sales 배열의 크기 - 1
links 배열의 각 원소는 [a, b] 형식, a는 팀장의 직원번호, b는 a팀장이 관리하는 팀원의 직원번호
비단말 노드는 자식 노드를 1번씩 모두 순회해야 되므로 DFS로 트리의 노드를 2번씩만 탐색하게 된다. → O(N)
주의할 점: 각 원소가 최대 10000을 가지고, sales의 전체 크기가 300,000 이므로 중간 결과가 정수 자료형의 범위를 벗어날 수 있음
정답 코드
#include <string>
#include <vector>
#define min(x,y) x < y ? x : y
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
vector<vector<int>> adj;
pll dfs(int root, vector<int>& sales) {
pll ret = {sales[root], 0};
if (adj[root].size() == 0) return ret;
vector<pll> subtrees;
for (auto& child : adj[root]) {
pll subtree = dfs(child, sales);
// 자신이 참석한 경우 서브 트리의 두 경우 중 작은 것을 포함
ret.first += min(subtree.first, subtree.second);
subtrees.push_back(subtree);
}
ret.second = 1e9;
for (int i = 0; i < subtrees.size(); i++) {
int minSum = subtrees[i].first; // i번째 자식이 반드시 참석한 경우
// 그 외 다른 서브 트리의 최소합의 합을 구함
for (int j = 0; j < adj[root].size(); j++) {
if (i == j) continue;
minSum += min(subtrees[j].first, subtrees[j].second);
}
// 모든 자식들 중 서브트리의 최소합이 가장 작은 것 계산
ret.second = min(ret.second, minSum);
}
return ret;
}
int solution(vector<int> sales, vector<vector<int>> links) {
adj = vector<vector<int>> (sales.size(), vector<int>());
for (auto& v : links) {
adj[v[0]-1].push_back(v[1]-1);
}
pll ret = dfs(0, sales);
return min(ret.first, ret.second);
}
