문제

아이디어

한 아이의 사탕을 뺏는다면 그 아이의 친구의 사탕을 전부 뺏어야 함을 주목하자.
즉, X명에게서 Y개의 사탕을 한 번에 뺏어가야 함을 알 수 있다.

K명 미만일 때 가장 많이 뺏을 수 있는 사탕을 구해야 하므로, 이를 0-1 배낭 문제로 치환하여 풀 수 있다.

아이들의 무리를 X의 weight, Y의 value 를 갖는 물건으로 치환하면, 최대 K-1의 용량을 갖는 배낭에 최대 value를 담는 배낭 문제가 된다.

아이들의 무리는 그래프 탐색을 통해 구한 후, 별도 클래스로 저장하도록 하자.

소스 코드

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

public class Main {
    static StringTokenizer st;
    static int n;
    static int m;
    static int k;
    static int[] candy;
    static boolean[] visited;
    static ArrayList<Integer>[] adj;
    static ArrayList<Kids> kids = new ArrayList<>();
    static int[][] dp;

    static class Kids {
        int num;
        int candy;

        Kids(int num, int candy) {
            this.num = num;
            this.candy = candy;
        }
    }

    static void bfs(int x) {
        ArrayList<Integer> queue = new ArrayList<>();

        queue.add(x);
        visited[x] = true;
        Kids k = new Kids(1, candy[x]);

        while (!queue.isEmpty()) {
            Integer cur = queue.remove(0);

            for (Integer adjKid : adj[cur]) {
                if (visited[adjKid]) continue;
                k.num++;
                k.candy += candy[adjKid];
                queue.add(adjKid);
                visited[adjKid] = true;
            }
        }

        kids.add(k);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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];
        visited = new boolean[n + 1];
        adj = new ArrayList[n + 1];
        for (int i = 0; i < n + 1; i++) {
            adj[i] = new ArrayList<>();
            visited[i] = false;
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < n + 1; 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());
            adj[a].add(b);
            adj[b].add(a);
        }

        for (int i = 1; i < n + 1; i++) {
            if (visited[i]) continue;
            else bfs(i);
        }

        dp = new int[kids.size() + 1][k]; // 캔디, 우는 애들 수

        for (int i = 0; i < kids.size() + 1; i++) {
            for (int j = 0; j < k; j++) {
                if (i == 0 || j == 0) dp[i][j] = 0;
                else if (kids.get(i - 1).num <= j) {
                    dp[i][j] = Math.max(kids.get(i - 1).candy + dp[i - 1][j - kids.get(i - 1).num], dp[i - 1][j]);
                } else dp[i][j] = dp[i - 1][j];
            }
        }

        System.out.println(dp[kids.size()][k - 1]);
    }
}

채점 결과

그래프 탐색 과정에서 removeFirst() 메서드를 사용했다.
Java 11 에는 제공되지 않음을 인지하고 있어 Java 15 로 제출했는데, 알고보니 Java 21 부터 지원되는 메서드였다.
remove(0) 으로 수정 후 제출했다.

이 문제를 푸니까 Solved.ac 5000등 안쪽으로 들어왔다.
말하는 감자인 내가 Solved.ac 에서는 상위 3%...?