[백준/BOJ] 백준 20303번 : 할로윈의 양아치

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

20303번: 할로윈의 양아치

유니온 파인드로 그룹을 만들고 int cache[3005][2]에 [뺏을 수 있는 인원수][0:이전의 결과, 1:새로운 결과] = 최대 사탕을 저장하여 그룹마다 확인하면서 계속 업데이트해 나아가면 cache[k - 1][0]에 결과값이 저장이 된다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, m, k;
vector<int> parent(30005);
vector<int> rank_size(30005);
vector<int> candy(30005);
vector<int> group_size(30005);
int cache[3005][2]; //[뺏을 수 있는 인원수][0:이전의 결과, 1:새로운 결과] = 최대 사탕
vector<pair<int, int>> people_candy; //(그룹의 인원수, 그룹의 사탕수)
vector<int> group_check(30005, 0);

void Pre()
{
	for (int i = 0; i < 30005; i++)
	{
		parent[i] = i;
		rank_size[i] = 1;
		group_size[i] = 1;
	}
}

int Find(int u)
{
	if (parent[u] == u)
		return u;

	return parent[u] = Find(parent[u]);
}

void Merge(int u, int v)
{
	u = Find(u);
	v = Find(v);

	if (u == v)
		return;

	if (rank_size[u] < rank_size[v])
	{
		parent[u] = v;
		group_size[v] += group_size[u];
		candy[v] += candy[u];
	}

	else
	{
		parent[v] = u;
		group_size[u] += group_size[v];
		candy[u] += candy[v];

		if (rank_size[u] == rank_size[v])
			rank_size[u]++;
	}
}

int Solve()
{
	for (int i = 0; i < people_candy.size(); i++)
	{
		int this_people = people_candy[i].first; //해당 그룹의 사람 수
		int this_candy = people_candy[i].second; //해당 그룹의 사탕

		//해당 인덱스에서 빼앗을 수 있는 사람의 수가 j명일때를 구한다
		for (int j = 0; j < k; j++)
		{
			//해당 그룹의 사탕을 빼앗을 수 없을때
			if (this_people > j)
			{
				cache[j][1] = cache[j][0];
			}

			//해당 그룹의 사탕을 빼앗을 수 있을때
			else
			{
				cache[j][1] = max(cache[j][0], cache[j - this_people][0] + this_candy);
			}
		}

		for (int j = 0; j < k; j++)
		{
			cache[j][0] = cache[j][1];
		}
	}

	return cache[k - 1][0];
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	Pre();

	cin >> n >> m >> k;

	for (int i = 1; i <= n; i++)
	{
		int input;
		cin >> input;

		candy[i] = input;
	}

	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;

		Merge(a, b);
	}

	for (int i = 1; i <= n; i++)
	{
		int this_group = Find(i);

		//이미 확인한 그룹일때
		if (group_check[this_group] == 1)
			continue;

		people_candy.push_back(make_pair(group_size[this_group], candy[this_group]));

		group_check[this_group] = 1;
	}

	int result = Solve();

	cout << result;


	return 0;
}