[Java | DP | 20303번 | 골2] 할로윈의 양아치

☑️ 문제

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

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, b가 주어진다. 이는 a와 b가 친구임을 의미한다. 같은 친구 관계가 두 번 주어지는 경우는 없다. (1≤a,b≤N, a≠b)

 

출력

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

 

예제 입력1

10 6 6
9 15 4 4 1 5 19 14 20 5
1 3
2 5
4 9
6 2
7 8
6 10

 

예제 출력1

57

 

예제 입력2

5 4 4
9 9 9 9 9
1 2
2 3
3 4
4 5

 

예제 출력2

0

 

☄️ 정답코드

import java.io.*;
import java.util.*;

public class Main {
    static int N, M, K;
    static int[] parent, size, candy;
    static List<int[]> groups = new ArrayList<>();
    static int[] dp;

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

    static void union(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        if (pa != pb) {
            parent[pb] = pa;
            size[pa] += size[pb];
            candy[pa] += candy[pb];
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        parent = new int[N + 1];
        size = new int[N + 1];
        candy = new int[N + 1];
        dp = new int[K];

        for (int i = 1; i <= N; i++) {
            parent[i] = i;
            size[i] = 1;
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            candy[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            union(a, b);
        }

        boolean[] visited = new boolean[N + 1];
        for (int i = 1; i <= N; i++) {
            int root = find(i);
            if (!visited[root]) {
                visited[root] = true;
                groups.add(new int[]{size[root], candy[root]});
            }
        }

        for (int[] group : groups) {
            int people = group[0];
            int totalCandy = group[1];

            for (int j = K - 1; j >= people; j--) {
                dp[j] = Math.max(dp[j], dp[j - people] + totalCandy);
            }
        }

        System.out.println(dp[K - 1]);
    }
}

 

🪐 풀이

DP + Union-Find

 

✅ Union-Find

친구들을 각 그룹으로 묶어주기 위해 Union-Find를 이용한다

 

✅ 그룹별로 DP

우선, 1번 아이부터 순회하면서 그룹을 파악합니다.

groups 안에 넣어주고, group을 순회하면서 dp를 채웁니다.

dp 채우는 방법은 knapsack으로 채우면 됩니다!!

boolean[] visited = new boolean[N + 1];
for (int i = 1; i <= N; i++) {
    int root = find(i);
    if (!visited[root]) {
      visited[root] = true;
      groups.add(new int[]{size[root], candy[root]});
    }
}

for (int[] group : groups) {
    int people = group[0];
    int totalCandy = group[1];

    for (int j = K - 1; j >= people; j--) {
      dp[j] = Math.max(dp[j], dp[j - people] + totalCandy);
    }
}