1135번: 뉴스 전하기

문제링크: 1135번: 뉴스 전하기

문제

민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다. 자기자신은 그들 자기 자신의 직접 또는 간접 상사가 아니고, 모든 직원은 민식이의 직접 또는 간접적인 부하이다.

민식이는 일단 자기 자신의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 뉴스를 들은 후에, 각 부하는 그의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 이 것은 모든 직원이 뉴스를 들을 때 까지 계속된다. 모든 사람은 자신의 직속 부하에게만 전화를 걸 수 있고, 전화는 정확하게 1분 걸린다. 이때 모든 직원이 소식을 듣는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

오민식의 사원 번호는 0이고, 다른 사원의 번호는 1부터 시작한다.

입력

첫째 줄에 직원의 수 N이 주어진다. 둘째 줄에는 0번 직원부터 그들의 상사의 번호가 주어진다. 0번 직원 (오민식)은 상사가 없기 때문에 -1이고, 나머지 직원 i의 상사 번호는 i보다 작거나 같은 음이 아닌 정수이다. N은 50보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 소식을 전하는데 걸리는 시간의 최솟값을 출력한다.

설명

트리구조에서 그리디하게 연락을 취하면 되는 문제이다. Root 노드는 0번 노드인것이 확정이므로 0번부터 탐색을 시작하면 된다.

dp[i]를 루트 노드를 i로 한 서브노드에서 전체 노드에 연락하는데 걸리는 시간으로 정의한다면 다음과 같이 점화식을 정할 수 있다.

dp[i] = max(dp[c]+c), c는 dp값이 큰 순서

위와 같이 점화식을 세우고 구현하면 문제가 해결되는데 서브트리에서 시간이 가장 오래걸리는 노드부터 연락을 하는 그리디한 구조를 찾았다면 쉽게 해결할 수 있는 문제였던것 같다.

코드

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#define endl '\n'
#define MAX 50

using namespace std;

int N, dp[MAX];
vector<vector<int>> child;

bool compare(pair<int, int> p1, pair<int, int> p2) {
	return p1.second > p2.second;
}

int getDP(int idx) {
	int& ret = dp[idx];
	if (ret != -1) return ret;

	// 부하가 없으면 0초
	if (child[idx].size() == 0) return ret = 0;

	vector<pair<int, int>> v;
	for (int i = 0; i < child[idx].size(); ++i) {
		int next = child[idx][i];
		int nextDP = getDP(next);
		v.push_back({ next,nextDP });
	}
	sort(v.begin(), v.end(), compare);
	for (int i = 0; i < v.size(); ++i) {
		ret = max(ret, v[i].second + i + 1);
	}
	return ret;
}

void solve() {
	cin >> N;
	memset(dp, -1, sizeof(dp));
	child.resize(N);
	for (int i = 0; i < N; ++i) {
		int a;
		cin >> a;
		if (a != -1) child[a].push_back(i);
	}

	cout << getDP(0);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
	//freopen("input.txt", "r", stdin);
	solve();
	return 0;
}