[BOJ] 백준 2533 사회망 서비스(SNS)

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

 Input 

8

1 2

1 3

1 4

2 5

2 6

4 7

4 8

 

 Output 

3

 

▶ 동적계획법(Dynamic Programming, DP) 

동적계획법(Dynamic Programming, DP)

 

"사회망 서비스에 속한 사람들은 얼리 어댑터이거나 얼리 어댑터가 아니다."

"얼리 어댑터가 아닌 사람들은 자신의 모든 친구들이 얼리 어댑터일 때만 이 아이디어를 받아들인다."

→ 두 사람이 친구 사이라면 적어도 둘 중 하나는 얼리 어댑터입니다.

 

 

Tree DP 방식

Root로부터 Top Down 방식으로 메모이제이션을 이용

E[i]: i번 학생을 얼리어댑터로 하지 않을 때, i 이하 서브트리에서 필요한 최소 얼리어댑터의 수.

       (child들이 모두 얼리어댑터이어야 하므로 child들의 D[j]값들의 합)

D[i]: i번 학생을 얼리어댑터로 할 때, i 이하 서브트리에서 필요한 최소 얼리어댑터의 수

       (i가 얼리어댑터이므로 child는 얼리어댑터이든 아니는 상관이 없다.)

 

 

※ Greedy 방식 + DFS를 이용한 풀이

[BOJ] 백준 2533 사회망 서비스(SNS) (Greedy)

 

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
const int LM = (int)1e6 + 5;
inline int min(int a, int b) { return a < b ? a : b; }
struct Node {
    int child;
    Node* next;
    Node* alloc(int nc, Node* np) {
        child = nc, next = np;
        return this;
    }
}buf[LM*2];
int bcnt;
int n, visit[LM], E[LM], D[LM];
Node* adj[LM];
 
void input() {
    scanf("%d", &n);
    int u, v;
    for (int i = 1; i < n; i++) {
        scanf("%d %d", &u, &v);
        // 양방향 연결
        adj[u] = buf[bcnt++].alloc(v, adj[u]);
        adj[v] = buf[bcnt++].alloc(u, adj[v]);
    }
}
 
void memoi(int now) {
    int eSum = 0, dSum = 1;
    visit[now] = 1;
    for (Node* p = adj[now]; p; p = p->next) {
        int child = p->child;
        if (visit[child] == 0) {
            memoi(child);
            eSum += D[child];
            dSum += min(E[child], D[child]);
        }
    }
    E[now] = eSum, D[now] = dSum;
}
 
int main() {
    input();
    memoi(1);
    printf("%d", min(E[1], D[1]));
}