Algorithm/BOJ
[백준 2533] 사회망 서비스(SNS) C++
Henu
2021. 5. 6. 01:22
2533번: 사회망 서비스(SNS)
페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망
www.acmicpc.net
트리에서의 다이나믹 프로그래밍 입문 #3
[백준 1949] 우수 마을 C++
1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1≤N≤10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며,
hyeo-noo.tistory.com
지난 포스팅 우수마을과 다르게
dp[now][0] -> 현재 친구가 얼리어답터가 아니라면 연결된 모든 친구는 얼리어답터여야 한다
이므로 dp[now][0] += dp[next][1]; 와 같이 쓸 수 있다
그리고 얼리어답터인 친구끼리 붙을 수 있기 때문에 아래와 같은 식을 통해 연결된 친구가 얼리어답터인지 아닌지 라는 2개의 경우에 따라 최솟값을 갱신한다
dp[now][1] += min(dp[next][0], dp[next][1]);
|
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
|
#include <iostream>
#include <vector>
using namespace std;
int N;
vector<int> tree[1000001];
// now가 루트일 때의 서브트리에서 얼리아답터의 최소 수
int dp[1000001][2];
bool visited[1000001];
void input(){
int u, v;
cin >> N;
for(int i = 0; i < N-1; i++){
cin >> u >> v;
tree[u].push_back(v);
tree[v].push_back(u);
}
}
void dfs(int now){
visited[now] = true;
dp[now][0] = 0;
dp[now][1] = 1;
for(int i = 0; i < tree[now].size(); i++){
int next = tree[now][i];
if(visited[next]) continue;
dfs(next);
dp[now][0] += dp[next][1];
dp[now][1] += min(dp[next][0], dp[next][1]);
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
input();
dfs(1);
cout << min(dp[1][0], dp[1][1]);
return 0;
}
|
cs |
dfs, 양방향 트리, 2차원 DP배열
미래의 나는 트리에서의 다이나믹 프로그래밍을 잊을 것이다
이걸 보고 다시 떠올려 주면 좋겠다