[BOJ/Gold 3] 백준 20303 할로윈의 양아치(C++)

문제 링크

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

20303번: 할로윈의 양아치

 

문제

Trick or Treat!!

10월 31일 할로윈의 밤에는 거리의 여기저기서 아이들이 친구들과 모여 사탕을 받기 위해 돌아다닌다. 올해 할로윈에도 어김없이 많은 아이가 할로윈을 즐겼지만 단 한 사람, 일찍부터 잠에 빠진 스브러스는 할로윈 밤을 즐길 수가 없었다. 뒤늦게 일어나 사탕을 얻기 위해 혼자 돌아다녀 보지만 이미 사탕은 바닥나 하나도 얻을 수 없었다.

단단히 화가 난 스브러스는 거리를 돌아다니며 다른 아이들의 사탕을 빼앗기로 마음을 먹는다. 다른 아이들보다 몸집이 큰 스브러스에게 사탕을 빼앗는 건 어렵지 않다. 또한, 스브러스는 매우 공평한 사람이기 때문에 한 아이의 사탕을 뺏으면 그 아이 친구들의 사탕도 모조리 뺏어버린다. (친구의 친구는 친구다?!)

사탕을 빼앗긴 아이들은 거리에 주저앉아 울고 K명 이상의 아이들이 울기 시작하면 울음소리가 공명하여 온 집의 어른들이 거리로 나온다. 스브러스가 어른들에게 들키지 않고 최대로 뺏을 수 있는 사탕의 양을 구하여라.

스브러스는 혼자 모든 집을 돌아다녔기 때문에 다른 아이들이 받은 사탕의 양을 모두 알고 있다. 또한, 모든 아이는 스브러스를 피해 갈 수 없다.

입력

첫째 줄에 정수 N, M, K가 주어진다. N은 거리에 있는 아이들의 수, M은 아이들의 친구 관계 수, K는 울음소리가 공명하기 위한 최소 아이의 수이다. (1≤N≤30 000, 0≤M≤100 000, 1≤K≤min{N, 3 000})

둘째 줄에는 아이들이 받은 사탕의 수를 나타내는 정수 c1,c2,⋯,cN이 주어진다. (1≤ci≤10 000)

셋째 줄부터 M개 줄에 갈쳐 각각의 줄에 정수 a, b가 주어진다. 이는 a와 b가 친구임을 의미한다. 같은 친구 관계가 두 번 주어지는 경우는 없다. (1≤a,b≤N, a≠b)

출력

스브러스가 어른들에게 들키지 않고 아이들로부터 뺏을 수 있는 최대 사탕의 수를 출력한다.

예제 입력 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

예제 출력 1

57

예제 입력 2

5 4 4
9 9 9 9 9
1 2
2 3
3 4
4 5

예제 출력 2

0

알고리즘 분류

• 유니온 파인드
• 배낭 문제

풀이

M개의 친구 관계를 유니온 파인드로 정리한다.

그리고 각 그룹별로 총 인원 수와 갖고 있는 사탕 개수의 총합을 구한다.

마지막으로 냅색 알고리즘을 사용해서 K명 미만에게 사탕을 뺏었을 때 최대 사탕의 개수를 구한다.

이 때, 2차원 배열 DP[30000][3000]을 선언한다. 이것은 i번째 친구 그룹까지 탐색했을 때, j명에게 사탕을 뺏었을 때 최대 사탕의 개수의 총합을 의미한다.

여기서 K명 이상이 되면 울음소리가 공명하여 모든 어른들이 밖으로 나오게 되어 실패하므로, 최대 K-1명의 어린 아이들에게서 사탕을 뺏어야 한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX_N 30001
#define MAX_K 3001
#define LL long long
#define INF 1e9

using namespace std;
int N, M, K;
int C[MAX_N];
int Parent[MAX_N];
vector<int> Friends[MAX_N];
int All_Candy[MAX_N];
int DP[MAX_N][MAX_K];
int Answer = 0;

void Init() {
	for (int i = 1; i < MAX_N; i++) {
		Parent[i] = i;
	}
}

int Find(int X) {
	if (Parent[X] == X) {
		return X;
	}
	return Parent[X] = Find(Parent[X]);
}

void Union(int X, int Y) {
	int PX = Find(X);
	int PY = Find(Y);
	if (PX <= PY) {
		Parent[PY] = PX;
	}
	else {
		Parent[PX] = PY;
	}
}

void Input() {
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		cin >> C[i];
	}
	for (int i = 0; i < M; i++) {
		int A, B;
		cin >> A >> B;
		Union(A, B);
	}
}

void Settings() {
	vector<int> Vec;
	for (int i = 1; i <= N; i++) {
		int P = Find(i);
		Friends[P].push_back(i);
		Vec.push_back(P);
	}
	sort(Vec.begin(), Vec.end());
	Vec.erase(unique(Vec.begin(), Vec.end()), Vec.end());
	for (int i = 0; i < Vec.size(); i++) {
		int Rep = Vec[i];
		for (int j = 0; j < Friends[Rep].size(); j++) {
			All_Candy[i] += C[Friends[Rep][j]];
		}
	}
	for (int i = 0; i < Vec.size(); i++) {
		int Cur = Vec[i];
		int Cnt = Friends[Cur].size();
		int Candy = All_Candy[i];
		for (int j = (K - 1); j >= 0; j--) {
			if (j - Cnt >= 0) {
				DP[i + 1][j] = max(DP[i][j], DP[i][j - Cnt] + Candy);
			}
			else {
				DP[i + 1][j] = DP[i][j];
			}
			Answer = max(Answer, DP[i + 1][j]);
		}
	}
}

void Find_Answer() {
	cout << Answer << "\n";
}

int main() {
	FASTIO
	Init();
	Input();
	Settings();
	Find_Answer();

	return 0;
}