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

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

20303번: 할로윈의 양아치

 

솔루션

---

친구들을 하나의 묶음으로 묶고 냅색을 수행하면 된다.

 

1. bfs를 이용해 그룹의 인원과, 사탕의 총 개수를 구한다.

2. 냅색을 이용한다..

 

 

 

(오랜만에 글을 써서.. 그런가.. 엄청 짧다..)

 

 

코드

---

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

int N, M, K;
int V[30002];
vector<int> edge[30002];

bool visit[30002];
int num = 0;

int dp[30002][3002];

vector<pair<int, int>> group;
void makeSet(int cur) {
	queue<int> Q;
	Q.push(cur);
	visit[cur] = true;

	int w = 0;
	int num = 0;
	while (!Q.empty()) {
		int cur = Q.front();
		Q.pop();
		num++;
		w += V[cur];

		for (auto& next : edge[cur]) {
			if (!visit[next]) {
				Q.push(next);
				visit[next] = true;
			}
		}
	}
	group.push_back({ num,w });

	return;
}

int solve(void) {
	
	for (int i = group[0].first; i < K; i++) {
		dp[0][i] = group[0].second;
	}

	for (int i = 1; i < group.size(); i++) {
		for (int j = 0; j < K; j++) {
			if (j - group[i].first >=0) {
				dp[i][j] = dp[i - 1][j - group[i].first] + group[i].second;
			}
			dp[i][j] = max(dp[i - 1][j], dp[i][j]);
		}
	}

	return dp[group.size() - 1][K - 1];
}

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

	cin >> N >> M >> K;

	for (int i = 1; i <= N; i++) {
		cin >> V[i];
	}

	for (int i = 0; i < M; i++) {
		int str, end;
		cin >> str >> end;
		
		edge[str].push_back(end);
		edge[end].push_back(str);
	}

	for (int i = 1; i <= N; i++) {
		if (!visit[i]) {
			num = 0;
			makeSet(i);
		}
	}

	cout << solve() << '\n';
}