[ boj : 20303 ] 할로윈의 양아치

www.acmicpc.net/problem/20303

20303번: 할로윈의 양아치

문제 : 아이들의 수 N, 관계 M, 울기 시작하는 최소의 수 K 가 주어질때 아이들이 울지 않을때 가질 수 있는 최대 사탕수를 구하여라

 

해설 : 일단 뭔가 보기엔 되게 복잡해 보이고 어려워 보이지만 문제를 단순화 시키면 쉽게 찾을 수 있으실 겁니다.

먼제 아이들의 관계가 주어졌고 "친구의 친구도 친구다" 라는 문구를 보고 disjointed-set 의 개념을 생각하시면 됩니다. 친구관계인 아이들을 전부 전처리로 묶어주고 난 후에 사탕의 수도 통합시켜주고 집합내에 있는 아이들의 수도 계산해 줍시다.

 

그리고 나면 우린 2가지의 정보를 얻은 상태입니다. 각 집합의 '사탕의 수','아이들의 수' 그럼 생각해볼만한게 모든 조합들을 뽑아서 최대값을 갱신하면 되지 않나 싶지만 각 아이들이 전부 친구가 존재하지 않는다면 3만개의 집합이 형성될거고 이는 조합으로는 풀 수 없다는 뜻이 됩니다.

 

냅색문제입니다. 

dp[i][j] = i가지의 집합을 선택하였고 j명의 아이들을 선택했을 경우 가질 수 있는 사탕의 최대갯수

 

이렇게 2차원배열을 선언해서 풀어줘도 충분히 해결가능하지만 이번 글에선 특별히 1차원의 상태배열을 만들어서 풀어보겠습니다.

저 2차원의 상태배열을 곰곰이 생각해보면 결국 기존값에 덮어씌우는 동작을 새로운 공간에 적어주는 것인데 이를 굳이 새로운 공간에 적어주지 않고 기존 정보를 갱신해주는 방식으로 해볼 수 있습니다.

어쩌면 "동전2"와 비슷한 문제일 수도 있습니다. 다만 주의할 점은 "동전2" 문제는 개수의 영향을 받지 않는다는 특징이 있지만 이는 오로지 각 집합이 1개씩만 존재합니다.

이럴때는 "바텀-업" 방식이 아닌 "탑-다운" 방식을 사용해서 쉽게 답을 도출 할 수 있습니다.

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int parent[30010];
int dp[3010];
int candy[30010],person[30010];

void union_parent(int x, int y);
int get_parent(int x);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n, m, k;
	int x,y;
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++)parent[i] = i;
	for (int i = 1; i <= n; i++) {
		cin >> candy[i];
		person[i] = 1;
	}
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		union_parent(x, y);
	}
	for(int i=1;i<=n;i++)
		if (parent[i] != i) {
			int p = get_parent(i);
			candy[p] += candy[i];
			person[p] += person[i];
		}

	for (int i = 1; i <= n; i++) {
		if (parent[i] != i)continue;
		for (int j = k - 1; j - person[i] >= 0; j--)
			dp[j] = max(dp[j], dp[j - person[i]] + candy[i]);
	}
	cout << dp[k - 1];	
	return 0;
}
void union_parent(int x, int y)
{
	x = get_parent(x);
	y = get_parent(y);
	
	if (x < y)parent[y] = x;
	else parent[x] = y;
}
int get_parent(int x)
{
	if (x == parent[x])return x;
	return parent[x] = get_parent(parent[x]);
}