[BOJ 2533] 사회망 서비스

일단 입력으로 트리가 주어지고 있으므로 가장 흔하고 쉽게 생각할 수 있는 DP설정을 사용하면

DP( i ) = i 를 root로 하는 subtree 의 최소 얼리 어답터 수,

하위문제 = DP( i 의 자식들 )

이와 같이 설정해 볼 수 있다.

이 상태에서 하위 문제들로 DP(i) 를 구하려고 해보면 일단,

i가 얼리어답터인지 여부에 따라 경우가 달라지므로 i 가 얼리어답터인 경우와 아닌 경우의 답을 구한 후 종합해야 문제가 쉬워짐을 알 수 있다.

 우선 i가 얼리어답터인 경우엔 자식 노드들에 대한 아무런 제약이 걸리지 않으므로 ‘ DP(i 의 자식들 )의 총합 + 1 ‘ 임을 쉽게 알 수 있다.

이제 문제는 i가 얼리어답터가 아닌 경우인데, 이 때는 문제 조건에 따라 자식 노드가 무조건 얼리어답터 여야만 한다.

하지만 앞서 설정한 DP 문제의 정보만으로는 이를 구하기 힘드므로 다음과 같은 새로운 정보가 필요하게 된다.

‘DP2( i ) = i가 얼리어답터일 경우, i 를 root로 하는 subtree 의 최소 얼리 어답터 수’

이제 이를 포함하기 위해 새롭게 DP 설정을 해보면

DP( i, j ) = i의 상태가 j인 경우, i 를 root로 하는 subtree 의 최소 얼리 어답터 수 

하위 문제 = DP( i 의 자식들, false ) , DP( i 의 자식들, true )

DP( i, true) = min(DP(i 의 자식, true), DP(i 의 자식, false))들의 총합 + 1

DP( i, false) = DP(i 의 자식, true) 들의 총합 

이와 같이 정의 할 수 있다.

// code by RiKang, weeklyps.com
#include <stdio.h>
#include <vector>
#include <algorithm>
 
using namespace::std;
 
int n;
int dp[1000005][2];
bool visited[1000005];
vector<int> child[1000005];
vector<int> edge[1000005];
 
void getchild(int now){
    visited[now] = true;
    for(int i=0 ; i<edge[now].size() ; i++){
        int next = edge[now][i];
        if(!visited[next]){
            child[now].push_back(next);
            getchild(next);
        }
    }
}
 
int getdp(int now,bool chk){
    if(dp[now][chk]!=0) return dp[now][chk];
    if(child[now].size()==0) return dp[now][chk] = chk;
    if(chk){
        int ans=0;
        for(int i=0 ; i<child[now].size() ; i++){
            int next = child[now][i];
            ans += min(getdp(next,false), getdp(next,true));
        }
        return dp[now][chk] = ans + 1;
    }
    else{
        int ans=0;
        for(int i=0 ; i<child[now].size() ; i++){
            int next = child[now][i];
            ans += getdp(next,true);
        }
        return dp[now][chk] = ans;
    }
}
 
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d %d",&u,&v);
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    getchild(1);
    printf("%d",min(getdp(1,false),getdp(1,true)));
}