BOJ 1135 - 뉴스 전하기

문제

임의의 트리가 주어지고 한 노드는 1분에 하나의 자식에게 전화할 수 있을 때, 루트에서 시작해 모든 노드가 전화를 받기까지 몇 분이 걸리는지 계산하는 문제이다.

풀이

한 노드에 대해, 자식 노드 각각을 루트로하는 서브 트리의 소요 시간이 많은 자식부터 전화를 해야 하기 때문에 bottom-up 방식으로 해결했다.

• \(Dp(i)\) : \(i\) 번째 노드를 루트노드로 하는 서브 트리의 모든 노드들이 전화를 받는데 걸리는 시간
  리프 노드의 경우 1
  • \(Dp(i)\) = 자식 노드들의 dp를 정렬한 배열에 대해, (자식 노드의 dp + 순서)의 최대값
    e.g. 배열이 [1, 2, 3, 5]일 경우, (5, 3, 2, 1) 순서로 전화를 해야 하기 때문에, [5+1, 3+2, 2+3, 1+4] 중 최대값인 6이 \(Dp(i)\)가 됨

소스코드

#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>

using namespace std;
using pii=pair<int, int>;
using vi=vector<int>;
using lld=long long;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, t;
	cin>>n;
	vi dp(n, 0);
	vector<vi> al(n, vi(0));
	for(int i=0;i<n;i++){
		cin>>t;
		if(t==-1) continue;
		al[t].push_back(i);
	}
	for(int i=n-1;i>-1;i--){
		if(al[i].size()==0){
			dp[i]=0;
			continue;
		}
		int m=0, cnt=0;
		vi tv;
		for(int j=0;j<al[i].size();j++){
			tv.push_back(dp[al[i][j]]);
		}
		sort(tv.begin(), tv.end());
		for(int j=0;j<tv.size();j++){
			tv[j]+=tv.size()-j;
			if(m<tv[j]) m=tv[j];
		}
		dp[i]=m;
	}
	cout<<dp[0];
	return 0;
}

풀고나서

• 처음에 점화식을 만들 때 자식 노드 dp의 최대값과 자식 노드들의 개수만 비교해서 WA를 받았다.