반응형
https://www.acmicpc.net/problem/2533
2533번: 사회망 서비스(SNS)
페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망
www.acmicpc.net
DP
dp[i][0]: 본인이 얼리어답터가 아님 -> 이웃 모두 얼리어답터
dp[i][1]: 본인이 얼리어답터임 -> 이웃 얼리어답터 상관 없이 작은 값
점화식
dp[now][0] += dp[next][1]
dp[now][1] += min(dp[next][0], dp[next][1])
간선 양방향 및 visited 쓰는 이유
간선 단방향으로 입력할 경우, 간선 a, b 순서가 바뀌면 값이 달라짐
8
1 2
1 3
1 4
2 5
2 6
4 7
4 8
8
2 1
3 1
4 1
5 2
6 2
7 4
8 4
진행과정
0123456
소스 코드
|
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
|
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
vector<vector<int> > v;
int n, a, b, visited[1000001];
int dp[1000001][2]; // dp[i][0]: 본인이 얼리어답터가 아님 -> 이웃 모두 얼리어답터
// dp[i][1]: 본인이 얼리어답터임 -> 얼리어답터 상관없음
void func(int now) {
dp[now][1] = 1;
for (int next : v[now]) {
if (!visited[next]) {
visited[next] = 1;
func(next);
dp[now][0] += dp[next][1];
dp[now][1] += min(dp[next][0], dp[next][1]);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
v.resize(n + 1);
rep(i, n-1) {
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
visited[1] = 1;
func(1);
cout << min(dp[1][0], dp[1][1]);
}
|
cs |
반응형