[BOJ] 20303 - 할로윈의 양아치

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

BOJ - 할로윈의 양아치

문제 유형: 유니온-파인드, 다이나믹 프로그래밍, 배낭 문제

문제 난이도: Gold III

시간 제한: 1초

메모리 제한: 1024MB

 

문제

Trick or Treat!!

10월 31일 할로윈의 밤에는 거리의 여기저기서 아이들이 친구들과 모여 사탕을 받기 위해 돌아다닌다. 올해 할로윈에도 어김없이 많은 아이가 할로윈을 즐겼지만 단 한 사람, 일찍부터 잠에 빠진 스브러스는 할로윈 밤을 즐길 수가 없었다. 뒤늦게 일어나 사탕을 얻기 위해 혼자 돌아다녀 보지만 이미 사탕은 바닥나 하나도 얻을 수 없었다.

단단히 화가 난 스브러스는 거리를 돌아다니며 다른 아이들의 사탕을 빼앗기로 마음을 먹는다. 다른 아이들보다 몸집이 큰 스브러스에게 사탕을 빼앗는 건 어렵지 않다. 또한, 스브러스는 매우 공평한 사람이기 때문에 한 아이의 사탕을 뺏으면 그 아이 친구들의 사탕도 모조리 뺏어버린다. (친구의 친구는 친구다?!)

사탕을 빼앗긴 아이들은 거리에 주저앉아 울고 K명 이상의 아이들이 울기 시작하면 울음소리가 공명하여 온 집의 어른들이 거리로 나온다. 스브러스가 어른들에게 들키지 않고 최대로 뺏을 수 있는 사탕의 양을 구하여라.

스브러스는 혼자 모든 집을 돌아다녔기 때문에 다른 아이들이 받은 사탕의 양을 모두 알고 있다. 또한, 모든 아이는 스브러스를 피해 갈 수 없다.

 

입력

첫째 줄에 정수 N, M, K가 주어진다. N은 거리에 있는 아이들의 수, M은 아이들의 친구 관계 수, K는 울음소리가 공명하기 위한 최소 아이의 수이다. (1≤N≤30 000, 0≤M≤100 000, 1≤K≤min{N,3 000})

둘째 줄에는 아이들이 받은 사탕의 수를 나타내는 정수 c1,c2,⋯,cN이 주어진다. (1≤ci≤10 000)

셋째 줄부터 M개 줄에 갈쳐 각각의 줄에 정수 a$a$, b$b$가 주어진다. 이는 a와 b가 친구임을 의미한다. 같은 친구 관계가 두 번 주어지는 경우는 없다. (1≤a,b≤N, a≠b)

 

출력

스브러스가 어른들에게 들키지 않고 아이들로부터 뺏을 수 있는 최대 사탕의 수를 출력한다.

 

풀이

유니온-파인드를 이용해서 아이들의 친구관계들을 그룹화한다.

여러 개의 그룹이 생기근데, <그룹 사탕 개수, 그룹 크기>꼴로 값을 저장해두고, 배낭 문제를 풀면 된다.

dp[i] = i명의 학생들로부터 뺏어서 최대 얻는 사탕 개수로 한다.

각 그룹정보를 읽으면서, k-1~0의 범위, 즉 역순으로 최대값을 업데이트해주면 된다. 역순으로 하는 이유는 중복 방지를 위해서이다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int n, m, k;
int candies[30001];
int parent[30001];
int groupsize[30001];

int getRoot(int x) {
  if (parent[x] == -1)
    return x;
  return parent[x] = getRoot(parent[x]);
}

void merge(int a, int b) {
  int ra = getRoot(a);
  int rb = getRoot(b);
  if (ra == rb)
    return;

  if (ra < rb)
    parent[rb] = ra;
  else
    parent[ra] = rb;
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  memset(parent, -1, sizeof(parent));

  cin >> n >> m >> k;

  for (int i = 1; i <= n; ++i) {
    cin >> candies[i];
    groupsize[i] = 1;
  }

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

  for (int i = 1; i <= n; ++i) {
    int root = getRoot(i);
    if (root != i) {
      groupsize[root]++;
      candies[root] += candies[i];
      candies[i] = 0;
      groupsize[i] = 0;
    }
  }

  vector<pair<int, int>> trees;
  for (int i = 1; i <= n; ++i) {
    if (groupsize[i] < k && candies[i] > 0) {
      trees.push_back({candies[i], groupsize[i]});
    }
  }

  int size = trees.size();
  if (size == 0) {
    cout << "0\n";
    return 0;
  }

  vector<int> dp(k, INT_MIN); // dp[i] = i명으로 만드는 최대
  dp[0] = 0;
  for (int i = 0; i < size; ++i) {
    for (int g = k - 1; g >= 0; --g) {
      int prev = g - trees[i].second;
      if (prev >= 0) {
        dp[g] = max(dp[g], dp[prev] + trees[i].first);
      }
    }
  }

  cout << *max_element(dp.begin(), dp.end()) << "\n";

  return 0;
}