https://www.acmicpc.net/problem/1135
1135번: 뉴스 전하기
민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다
www.acmicpc.net
서론
이게 왜 DP인지 모르겠다. DP는 부분 문제 중복 계산을 방지하는 기믹이 반드시 들어가야 하는데 이 문제에는 그런게 전혀 없다. 애초에 N이 너무 작기도하고 트리 자료구조 상 한 루트를 탐색하면 그 루트를 다시 접근할 이유가 전혀 없다. DP 아닌 것 같음. 단순 트리 순회 문제가 왜 골2임. 어제 푼 짚신벌레가 훨씬 어려웠다.
풀이
1명 씩만 통화할 수 있으므로 가장 처리가 오래 걸릴 직속 부하부터 먼저 전화해야한다.
직속 부하들을 소요되는 시간으로 내림차순 정렬하고, i번째로 부하에게 +i를 하면 통화마다 걸리는 시간을 알 수 있다.
그 중 가장 시간이 오래걸리는 통화가 현재 단계의 최종 시간이 된다. DFS로 각 단계마다 재귀적으로 계산해 답을 구한다.
코드
더보기
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int n; vector<vector<int>> arr; vector<int> dp;
int r(int cur) {
int& ret = dp[cur];
//if (ret != 0) return ret; // 왜 DP임 이게 ?
vector<int> li;
if (arr[cur].size() == 0) return 0;
for (const auto& cn : arr[cur]) {
li.push_back(r(cn));
}
sort(li.begin(), li.end());
int ti = li.size();
for (auto& cn : li) {
cn += ti--;
}
sort(li.begin(), li.end());
ret = li[li.size() - 1];
return ret;
}
int main() {
cin >> n; arr.resize(n); dp.resize(n);
for (int i = 0; i < n; i++) {
int t; cin >> t;
if (t != -1) {
arr[t].push_back(i);
}
}
cout << r(0);
return 0;
}