(2533) 사회망 서비스(SNS)

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

단계별로 풀어보기

36단계(트리에서의 동적 계획법) 3번째

 

 

 

이전 문제인 우수 마을과 매우 유사하다.

1번 사람을 루트 노드로 가정했을 때,

dp[x]는 x번 사람을 루트로 하는 서브트리에서 얼리어답터 수의 최소값이다.

dp[x][0]은 x번 사람이 일반인인 경우, dp[x][1]은 x번 사람이 얼리어답터 경우다.

x번 사람이 얼리어답터가 아니라면 주변 사람은 전부 얼리어답터야 하므로 dp[x][0]에는 dp[y][1]을 더해준다.

x번 사람이 얼리어답터라면 주변 사람은 상관 없으므로 dp[y][0]과 dp[y][1] 중 작은 값을 더해준다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector adj(n+1, vector<int>()), dp(n+1, vector<int>(2));
  
  for(int i=1;i<n;i++){
    int a, b;
    
    cin >> a >> b;
    
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  
  auto dfs= [&](auto self, int now) -> void {
    dp[now][1]= 1;
    
    for(int next:adj[now]){
      if(dp[next][1])  continue;
      
      self(self, next);
      dp[now][0]+= dp[next][1];
      dp[now][1]+= min(dp[next][0],dp[next][1]);
    }
  };
  
  dfs(dfs, 1);
  
  cout << min(dp[1][0], dp[1][1]);
  
  return 0;
}