백준 20303 - 할로윈의 양아치

 

해결과정 - 냅색, 분리집합

문제의 첫번째 핵심은 동일한 집단에 존재하는 학생 수와 캔디수를 분리해 놔야 한다. 이 방법은 분리집합과 dfs를 사용한 cycle을 통해 구할 수 있는데 분리집합이 간편하므로 이를 사용하였다.

 

두번째 핵심은 구한 집단을 통해 K를 넘지 않는 그룹들 찾기 문제인데 잘 떠올려 보면 냅색과 동일한 문제라는 것을 알 수 있다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <stack>
#include <cmath>
#include <unordered_map>

#define FAST ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

typedef long long ll;

using namespace std;

vector<int> parent;
vector<pair<int, int>> Group;
vector<pair<int, int>> group;

int n, m, k;

int dp[3001][30001];

int find(int i) {
    if (parent[i] == i) return i;
    return parent[i] = find(parent[i]);
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);

	if (a == b) return;

    if(a > b) swap(a, b);
	parent[b] = a;

    group[a].first += group[b].first;
	group[a].second += group[b].second;
	group[b] = {0, 0};
}

int main() {
    FAST;
    
    cin >> n >> m >> k;

    parent.resize(n + 1);
    group.resize(n + 1);

    // 부모 캔디 소지개수 초기화
    for (int i = 1; i <= n; i++) {
        int candy;
        cin >> candy;
		parent[i] = i;
        // 총 캔디의 개수 와 그룹 인원 
        group[i] = { candy, 1 };
	}

    //그룹 초기화
    for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
        merge(a, b);
	}

    //남은 그룹 확인
    for (int i = 1; i <= n; i++) {
		if (group[i].first == 0) continue;
		
        Group.push_back({ group[i].first , group[i].second});
	}

    sort(Group.begin(), Group.end(), [](pair<int, int>& a, pair<int, int>& b){
        if(a.second == b.second) return a.first > b.first;
        return a.second < b.second;
        });



    for (int i = 1; i <= Group.size(); i++) {
		int candy = Group[i - 1].first;
        int people = Group[i - 1].second;

        for (int j = 1; j <= k; j++) {
            if (people >= j) dp[j][i] = dp[j][i - 1];
            else dp[j][i] = max(dp[j][i - 1], dp[j - people][i - 1] + candy);
        }
	}
  
    cout << dp[k][Group.size()] << "\n";
    return 0;
}

 

후기

솔직하게 말하면 처음에 냅색 방식이 아닌 dfs 방식으로 이 문제를 풀다 시간초과가 나서 애먹었다..

학부수준의 지식으로 풀수있는 정말 좋은 문제이다