[백준] No.1135 - 뉴스 전하기 (C++, 그리디)

문제

 

https://www.acmicpc.net/problem/1135

1135번: 뉴스 전하기

 

풀이

 

solved.ac 난이도: Gold 1

 

자신의 직속 부하가 최고 상관인 서브 트리들에서의 최소 전파 시간을 구한 값을 배열에 저장한다 생각해보자.

부하의 서브 트리들 중에서 가장 전파 시간이 오래 걸리 트리는 언제 방문해야 최단 시간을 구할 수 있을까?

조금만 생각해보면 당연히 전파 시간이 오래 걸리는 순서대로 먼저 방문해야 항상 이득임을 알 수 있다.

(오래 걸리는 트리를 늦게 방문할수록 전체 전파시간이 늘어날 가능성이 있다.)

 

추가적으로 직속 부하에게 전달하는 시간에는 1분이 걸리므로 직속 부하의 수를 n이라 하면 자신의 직속 부하에게 모두 전화를 돌리는 데는 n분의 시간이 걸린다.

따라서 전파 시간이 오래걸리는 순으로 정렬한 후, 해당 전파 시간 + 정렬 순서(직속 부하에게 전화를 거는데 걸리는 시간) 중에 가장 큰 값이 해당 서브 트리의 최단 전파 시간이 된다. 

 

 

int MinPropaDFS(int idx){
  if(chilidren[idx].empty())
    return 0;
 
  vector<int> sub_answer;
  for(int i=0; i<chilidren[idx].size() ; ++i)
    sub_answer.push_back(MinPropaDFS(chilidren[idx][i]));
  
  sort(sub_answer.begin(), sub_answer.end(), greater());
 
  int ret = 0;
  for(int i=0; i<sub_answer.size() ; ++i)
    ret = max(ret, sub_answer[i] + (i+1));
 
  return ret;
}

 

 

코드