Algorithm/problem

백준 2533 : 사회망 서비스(SNS) - 트리 DP, C++

DingCoDing 2022. 10. 3. 20:27
반응형

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

 

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

첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에

www.acmicpc.net

#include <bits/stdc++.h>
using namespace std;
#define MX 1000001


int N, dp[MX][2];
vector<int> adj[MX];
bool vis[MX];

void DFS(int node){
    vis[node] = 1;

    dp[node][0] = 1;
    for(auto nx : adj[node]){
        if(vis[nx]) continue;
        DFS(nx);

        dp[node][0] += min(dp[nx][0], dp[nx][1]);
        dp[node][1] += dp[nx][0];
    }
}


int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> N;
    for(int i=0; i<N-1; i++){
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    DFS(1);

    cout << min(dp[1][0], dp[1][1]) << '\n';


    return 0;
}
반응형