[백준 C++] 20303번: 할로윈의 양아치

1. 문제

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

20303번: 할로윈의 양아치

 

2. 알고리즘 분류

• 다이나믹 프로그래밍
• 자료 구조
• 그래프 이론
• 그래프 탐색
• 분리 집합
• 배낭 문제

 

3. 소스 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N, M, K;
int candy[30001];
int total_candy[30001];
int root[30001];
vector<int> group;
vector<int> friends[30001];
int dp[30004][3003];

int Find(int a)
{
	if (root[a] == a)
		return a;

	return root[a] = Find(root[a]);
}

void Union(int a, int b)
{
	int pA = Find(a);
	int pB = Find(b);

	if (pA <= pB)
		root[pB] = pA;
	else
		root[pA] = pB;
}

int main()
{
	// Fast IO
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// 초기화
	for (int i = 0; i < 30001; i++)
		root[i] = i;

	// N : 거리의 있는 아이의 수, M : 아이들의 친구 관계 수, K : 울음소리가 공명하기 위한 최소 아이의 수
	cin >> N >> M >> K;

	// 아이들이 받은 사탕의 수 입력
	for (int i = 1; i <= N; i++)
		cin >> candy[i];


	// 친구 관계 입력
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		Union(a, b);
	}

	for (int a = 1; a <= N; a++) {
		int pA = Find(a);	// 대표자 찾기
		friends[pA].push_back(a);	// 대표자 기준 친구 추가
		group.push_back(pA);	// 대표자 그룹에 추가
	}

	// 대표자 중복제거
	sort(group.begin(), group.end());
	group.erase(unique(group.begin(), group.end()), group.end());

	// 대표자 기준으로 친구들 캔디 총합 계산
	for (int i = 0; i < group.size(); i++) {
		int rep = group[i];
		for (int j = 0; j < friends[rep].size(); j++)
			total_candy[i] += candy[friends[rep][j]];
	}

	int ans = 0;

	/* 배낭 문제 알고리즘
	dp[i][j] = i번째 그룹까지 탐색했고, 울음소리가 공명하기 위한 최소 아이의 수가 j일 떄, 최대 얻을 수 있는 candy 갯수
	case 1) 현재까지 모인 아이의 수가 울음소리가 공명하기 위한 최소아이의 수 j 값보다 클 경우,
	case 2) 현재까지 모인 아이의 수가 j 값보다 작거나 같을 경우
	*/
	for (int i = 0; i < group.size(); i++) {
		int friend_cnt = friends[group[i]].size();
		for (int j = 0; j < K; j++) {
			if (j - friend_cnt >= 0)	// case 1
				dp[i + 1][j] = max(dp[i][j], dp[i][j - friend_cnt] + total_candy[i]);
			else   // case 2
				dp[i + 1][j] = dp[i][j];

			ans = max(ans, dp[i + 1][j]);
		}
	}

	cout << ans << '\n';

	return 0;
}

 

4. 유용한 알고리즘/문법

1) Union-Find (분리 집합)

int Find(int a)
{
	if (root[a] == a)
		return a;

	return root[a] = Find(root[a]);
}

void Union(int a, int b)
{
	int pA = Find(a);
	int pB = Find(b);

	if (pA <= pB)
		root[pB] = pA;
	else
		root[pA] = pB;
}

 

2) Vector 중복 제거

// 대표자 중복제거
sort(group.begin(), group.end());
group.erase(unique(group.begin(), group.end()), group.end());

 

3) 배낭 문제 알고리즘

	/* 배낭 문제 알고리즘
	dp[i][j] = i번째 그룹까지 탐색했고, 울음소리가 공명하기 위한 최소 아이의 수가 j일 떄, 최대 얻을 수 있는 candy 갯수
	case 1) 현재까지 모인 아이의 수가 울음소리가 공명하기 위한 최소아이의 수 j 값보다 클 경우,
	case 2) 현재까지 모인 아이의 수가 j 값보다 작거나 같을 경우
	*/
	for (int i = 0; i < group.size(); i++) {
		int friend_cnt = friends[group[i]].size();
		for (int j = 0; j < K; j++) {
			if (j - friend_cnt >= 0)	// case 1
				dp[i + 1][j] = max(dp[i][j], dp[i][j - friend_cnt] + total_candy[i]);
			else   // case 2
				dp[i + 1][j] = dp[i][j];

			ans = max(ans, dp[i + 1][j]);
		}
	}