티스토리 뷰

문제 풀이

[BOJ 2533] 사회망 서비스

RiKang 2017. 10. 31. 17:26

일단 입력으로 트리가 주어지고 있으므로 가장 흔하고 쉽게 생각할 수 있는 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) 들의 총합 


이와 같이 정의 할 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// 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]!=0return dp[now][chk];
    if(child[now].size()==0return 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)));
}
cs


'문제 풀이' 카테고리의 다른 글

[CF 371 D] Animals and Puzzle  (0) 2017.10.31
[BOJ 4008] 특공대  (0) 2017.10.31
[CF 146 B] Let's Play Osu!  (0) 2017.10.31
[BOJ 2533] 사회망 서비스  (0) 2017.10.31
[BOJ 5060] 무글 맵스  (0) 2017.10.31
[BOJ 2057] 계단 오르기  (0) 2017.10.31