[백준] 1135 뉴스 전하기 (복습)

문제

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

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

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

입력

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

출력

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

 

상사가 직속 부하에게 한번에 한명에게만 뉴스를 전달할 수 있고 , 시간은 1이 소요됩니다.

따라서 트리 위 한 사람기준으로 뉴스를 모두에게 전달하기까지 걸리는 시간으로는,

직속부하에게 나누어주는 시간과 직속부하가 그 부하에게 나누어주는 시간을 모두 고려해야합니다.

따라서 이는 DP문제로, 재귀형태로 풀 수 있습니다.

 

A의 부하 a b 가 있다고 가정하면, A는 부하a,b에게 뉴스를 전달하는데 각각 1, 2초씩 걸립니다.

부하 a,b가 자신의 부하에게 뉴스를 전달하는데 각각 5초, 3초씩 걸린다고 할 때

A는 a에게 먼저 뉴스를 전달하고 b에게 전달해야 더 빠르게 모든 뉴스를 전달할 수 있을것입니다.

따라서, A의 직속부하가 걸리는 시간에 대해서 정렬하고(5초, 3초)

뉴스를 전달하는 시간(1초, 2초)를 각각에대해 더해주면 (6초 5초)

모든 뉴스를 전달하는데 총 6초가 걸립니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL)
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 9876543210;
int n, arr[51], x;
vi adj[51];
int dfs(int k) {
	vi v;
	for (auto r : adj[k]) {
		dfs(r);
		v.push_back(arr[r]);
	}
	sort(v.begin(), v.end());
	rep(i, v.size()) {
		v[i] += (adj[k].size() - i);
	}
	if(v.size())
		arr[k] = *max_element(v.begin(), v.end());
	return arr[k];
}
int main() {
	FAST;
	cin >> n >> x;
	REP(i, n-1) {
		cin >> x;
		adj[x].push_back(i);
	}
	cout<<dfs(0);
}

 

 

 

 

점화식이 살짝 복잡합니다. 수도코드는 다음과 같습니다.

DFS(노드 K){

    vector temp

    for each 자식노드 C: adj[K]{

        temp.push(DFS(C))

    }

    sort(temp)

    for each V ,i=temp.size;i-- : temp{

    V+=i

    }

    dp[K]=maxElement(temp)

    }

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 };
int N, x, dp[51];
vi adj[51];
int dfs(int k) {
	vi temp;
	for (auto c : adj[k]) {
		temp.push_back(dfs(c));
	}
	if (temp.size()) {
		sort(temp.begin(), temp.end());
		rep(i, temp.size()) {
			temp[i] += (temp.size() - i);
		}
		return dp[k] += *max_element(temp.begin(), temp.end());
	}
	return 0;
}
int main() {
	cin >> N;
	rep(i, N) {
		cin >> x;
		if (x != -1)adj[x].push_back(i);
	}
	cout << dfs(0);
}

그리디하게 dFS값이 가장 큰 자식노드에게 가장 우선적으로 뉴스를 전달합니다. 그렇게 모두 전달하고, 가장 오래걸린시간기준으로 값을 저장합니다.