[백준 C++] 20303번 할로윈의 양아치
백준 15681번 트리와 쿼리 cpp c++로 풀이
20303번: 할로윈의 양아치
문제 요약
문제
Trick or Treat!!
10월 31일 할로윈의 밤에는 거리의 여기저기서 아이들이 친구들과 모여 사탕을 받기 위해 돌아다닌다. 올해 할로윈에도 어김없이 많은 아이가 할로윈을 즐겼지만 단 한 사람, 일찍부터 잠에 빠진 스브러스는 할로윈 밤을 즐길 수가 없었다. 뒤늦게 일어나 사탕을 얻기 위해 혼자 돌아다녀 보지만 이미 사탕은 바닥나 하나도 얻을 수 없었다.
단단히 화가 난 스브러스는 거리를 돌아다니며 다른 아이들의 사탕을 빼앗기로 마음을 먹는다. 다른 아이들보다 몸집이 큰 스브러스에게 사탕을 빼앗는 건 어렵지 않다. 또한, 스브러스는 매우 공평한 사람이기 때문에 한 아이의 사탕을 뺏으면 그 아이 친구들의 사탕도 모조리 뺏어버린다. (친구의 친구는 친구다?!)
사탕을 빼앗긴 아이들은 거리에 주저앉아 울고 $K$명 이상의 아이들이 울기 시작하면 울음소리가 공명하여 온 집의 어른들이 거리로 나온다. 스브러스가 어른들에게 들키지 않고 최대로 뺏을 수 있는 사탕의 양을 구하여라.
스브러스는 혼자 모든 집을 돌아다녔기 때문에 다른 아이들이 받은 사탕의 양을 모두 알고 있다. 또한, 모든 아이는 스브러스를 피해 갈 수 없다.
사용 알고리즘
동적 계획법, 분리 집합
입출력
- 입력: 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, $1 \leq K \leq \min\left{N, 3\ 000\right}$) 둘째 줄에는 아이들이 받은 사탕의 수를 나타내는 정수 $c_1, c_2, \cdots, c_N$이 주어진다. ($1 \leq c_i \leq 10\ 000$) 셋째 줄부터 $M$개 줄에 갈쳐 각각의 줄에 정수 $a$, $b$가 주어진다. 이는 $a$와 $b$가 친구임을 의미한다. 같은 친구 관계가 두 번 주어지는 경우는 없다. ($1 \leq a, b \leq N$, $a \neq b$)
- 출력: 스브러스가 어른들에게 들키지 않고 아이들로부터 뺏을 수 있는 최대 사탕의 수를 출력한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
예제1
입력
10 6 6
9 15 4 4 1 5 19 14 20 5
1 3
2 5
4 9
6 2
7 8
6 10
출력
57
풀이
분리 집합과 dp를 사용하는 문제이다. 전형적인 분리 집합과 전형적인 배낭 문제를 한 문제로 합쳐 놓은 것이다. 먼저 서로에게 알리는 친구 무리를 분리 집합으로 구하여야 한다. 그 후 그것을 배낭 문제로 생각하여 풀면 된다. dp는 이차원으로 설정하여 한 축은 친구 무리들 한 축은 아이들의 수로 하여 풀면 된다.
어려웠던 점
분리 집합까지는 쉬웠는데 배낭 문제 구현이 어려웠다.
배운 점 / 느낀 점
배낭 문제 dp를 알게 되었다.
전체 코드
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
int n, m, k;
vector<int> candys;
vector<int> friends;
unordered_map<int, int> cf;
vector<pair<int,int>> candycandy;
vector<vector<int>> dp;
int mc;
int find(int a){
if(friends[a] == a){
return a;
}
else{
friends[a] = find(friends[a]);
return friends[a];
}
}
void add(int a, int b){
int aa = find(a);
int bb = find(b);
if(aa != bb){
friends[aa] = bb;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> m >> k;
candys = vector<int>(n);
candycandy = vector<pair<int,int>>();
friends = vector<int>(n+1);
cf = unordered_map<int, int>();
for (int i = 0; i < n; i++) {
cin >> candys[i];
friends[i+1] = i+1;
}
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
add(a, b);
}
for (int i = 0; i < n; i++) {
if(cf.find(find(i+1)) != cf.end()){
candycandy[cf[find(i+1)]].first += 1;
candycandy[cf[find(i+1)]].second += candys[i];
}
else{
cf[find(i+1)] = candycandy.size();
candycandy.push_back({1, candys[i]});
}
}
dp = vector<vector<int>>(candycandy.size()+1, vector<int>(k, 0));
for (int i = 1; i < candycandy.size()+1; i++) {
for (int j = 0; j < k; j++) {
if(j >= candycandy[i-1].first)
dp[i][j] = max(dp[i-1][j], dp[i-1][j-candycandy[i-1].first]+candycandy[i-1].second);
else{
dp[i][j] = dp[i-1][j];
}
mc = max(mc, dp[i][j]);
}
}
cout << mc;
return 0;
}