https://www.acmicpc.net/problem/1135
1135번: 뉴스 전하기
민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다
www.acmicpc.net
TreeDP는 난이도도 생각보다 높고, 많이 못 풀어봤어서 그런지 어렵네요..
0번 직원부터 시작해서 모든 직원에게 뉴스를 전하는데 최소 시간을 구하는 문제입니다.
한 번에 한 명에게만 전파가 가능하므로 전파하는 시간이 가장 오래걸리는 직속 부하에게 먼저 전파를 해야합니다.
list라는 벡터에 자신의 직속 부하에게 전파하는 시간을 모두 저장한 후에 내림차순으로 정렬합니다.
먼저 전파하는 부하에게는 추가적인 시간이 필요하지 않으므로 +0,
두 번째 전파하는 부하에게는 추가적인 시간이 +1,
마지막에 전파하는 부하에게는 list.size() - 1 만큼 추가적인 시간이 추가됩니다.
이 경우들의 최댓값이 자신의 부하직원에게 소식을 전하는데 걸리는 최소 시간입니다.
24번째 줄 +1을 한 이유는 부하가 없는 직원에게서 오는 값은 0이기 때문에 1을 더한 것입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 50
using namespace std;
vector<int> graph[MAX];
int N;
int dfs(int v) {
vector<int> list;
int ret = 0;
for (int i = 0; i < graph[v].size(); i++) {
int next = graph[v][i];
list.push_back(dfs(next));
}
sort(list.begin(), list.end(), [](int a, int b) {
return a > b;
});
for (int i = 0; i < list.size(); i++) {
ret = max(ret, list[i] + i + 1);
}
return ret;
}
void func() {
cout << dfs(0) << '\n';
}
void input() {
int x;
cin >> N >> x;
for (int i = 1; i < N; i++) {
cin >> x;
graph[x].push_back(i);
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 3673 나눌 수 있는 부분 수열 (0) | 2022.01.31 |
|---|---|
| boj 20500 Ezreal 여눈부터 가네 ㅈㅈ (0) | 2022.01.01 |
| boj 17090 미로 탈출하기 (0) | 2021.06.27 |
| boj 1648 격자판 채우기 (0) | 2021.06.22 |
| boj 14700 넴모넴모 (Hard) (0) | 2021.06.22 |