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

문제 링크

www.acmicpc.net/problem/2533

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

 

풀이

간단한 트리 DP 문제입니다.

1) 만약 현재 정점을 고르면 -> 자식들은 골라도 되고, 안골라도 됩니다.

2) 만약 현재 정점을 고르지 않으면 -> 모든 자식들을 골라야 합니다.

 

$d[now][k]$를 k가 0일때 안고름, 1일 때 고르는 상황의 최솟값이라고 합시다.

now의 모든 자식 next에 대해

$d[now][0] = \text{sum}(d[next][1])$

$d[now][1] = \text{sum(min}(d[next][0], d[next][1])) + 1$

입니다.

 

 

정답 코드

#include <bits/stdc++.h>

using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;

int n, d[1'111'111][2]; // 0이면 안고름, 1이면 고름
vvi p;
bool chk[1'111'111];

void go(int now) {
    chk[now] = true;
    d[now][1] = 1;
    for (int next: p[now]) {
        if (chk[next]) continue;
        go(next);
        d[now][0] += d[next][1];
        d[now][1] += min(d[next][0], d[next][1]);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    p.resize(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        p[u].push_back(v);
        p[v].push_back(u);
    }
    go(1);
    cout << min(d[1][0], d[1][1]);
}