[백준] 20303: 할로윈의 양아치 - JAVA

04 Jul 2023 in Algorithm on 다이나믹 프로그래밍

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

풀이

dp와 분리집합을 이용하는 문제.

사탕을 최대로 뺏어야 하는 문제였다.

친구들로부터 사탕을 뺏는데, K명 미만으로부터 사탕을 빼앗아야 한다.

한 친구의 사탕을 뺏으면 그와 친구인 친구들의 사탕을 함께 뺏는다.

각 친구별로 사탕의 개수를 알고 있고, 누구와 친구 관계를 갖고있는지 주어진다.

따라서, 분리집합(union-find)을 이용해 친구별로 그룹을 만들어 그룹별로 몇 명인지 몇 개의 사탕을 가지고 있는지 저장한다.

저장된 자료를 통해 배낭문제 알고리즘을 적용하여 최대 K-1명일 때 최댓값을 구했다.

---

메모리: 875636KB

시간: 1152ms

언어: Java 11

코드

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

public class Main {
    static class Node {
        int cost;
        long value;

        public Node(int cost, long value) {
            this.cost = cost;
            this.value = value;
        }
    }

    static int N, M, K;
    static int[] candy, person, group;
    static List<Node> list = new ArrayList<>();

    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());

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

        person = new int[N + 1];
        Arrays.fill(person, 1);

        group = new int[N + 1];
        for (int i = 1; i < N + 1; i++) {
            group[i] = i;
        }

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

        makeList();

        System.out.println(doDp());
    }

    private static long doDp() {
        long[][] dp = new long[list.size() + 1][K];

        for (int i = 1; i < list.size() + 1; i++) {
            int cost = list.get(i - 1).cost;
            long value = list.get(i - 1).value;

            for (int j = 0; j < K; j++) {
                if (cost <= j) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - cost] + value);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

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

    private static void makeList() {
        for (int i = 1; i < N + 1; i++) {
            if (group[i] != i) {
                int p = findGroup(i);
                candy[p] += candy[i];
                person[p] += person[i];
            }
        }

        for (int i = 1; i < N + 1; i++) {
            if (group[i] == i) {
                list.add(new Node(person[i], candy[i]));
            }
        }
    }

    private static void makeGroup(int a, int b) {
        int pa = findGroup(a);
        int pb = findGroup(b);

        if (pa < pb) {
            group[pb] = pa;
        } else {
            group[pa] = pb;
        }
    }

    private static int findGroup(int a) {
        if (a == group[a]) {
            return a;
        }
        return group[a] = findGroup(group[a]);
    }

}