민식이는 트리의 루트이다.
그의 직속 부하에게 한번에 한사람씩 전화를 하는데 1분이 소모된다.
모든 사람들이 전화를 받기까지 걸리는 최소시간을 구하는 문제다.
처음에는 문제를 잘못이해해서 모든 전화의 시작은 민식으로부터 시작되는줄 알았다.
두번 째는 현재위치에서 갈 수 있는 가장 depth가 깊은곳을 먼저 가는것으로 해주었다.
이것은 최적값이 아니다.
세번째는 현재위치에서 가장 많은 사람이 있는 곳으로 먼저 가도록 해주었다.
이것 또한 최적값이 아니다.
정확한 풀이는 다음과 같다.
현재위치에서 갈 수 있는 다음위치의 subtree의 모든 사람들이 전화를 받는
최소시간이 가장 큰곳으로 먼저 가야한다.
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int N;
vector<int> adj[51];
priority_queue<pair<int, int>> pq[51];
int dfs(int here) {
int ret = 0;
int plus = 0;
for (int &next : adj[here]) {
pq[here].push({ 1 + dfs(next), next });
}
while (!pq[here].empty()) {
int cost = pq[here].top().first;
int next = pq[here].top().second;
pq[here].pop();
ret = max(ret, cost + plus++);
}
return ret;
}
int main() {
scanf("%d", &N);
for (int n = 0;n < N;n++) {
int u;
scanf("%d", &u);
if (!n) continue;
adj[u].push_back(n);
}
printf("%d\n", dfs(0));
return 0;
}
| cs |
Top-Down 방식으로 풀리는 좋은 문제였다.
댓글 없음:
댓글 쓰기