[백준 20303번] 할로윈의 양아치

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

 

package graph;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Graph20303 {
    static int[] parent;
    static int[] candy;

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

    static void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);

        if (rootA != rootB) parent[rootB] = rootA;
    }

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

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 아이 수
        int M = Integer.parseInt(st.nextToken()); // 친구 관계 수
        int K = Integer.parseInt(st.nextToken()); // 최대 괴롭힐 수 있는 아이 수 (제한)

        candy = new int[N + 1];
        parent = new int[N + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            candy[i] = Integer.parseInt(st.nextToken());
            parent[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());
            union(a, b);
        }

        // map에 그룹별 담기
        Map<Integer, int[]> groupMap = new HashMap<>();

        for (int i = 1; i <= N; i++) {
            int root = find(i);
            groupMap.putIfAbsent(root, new int[]{0, 0}); // 있으면 안넣고 없으면 넣어라
            groupMap.get(root)[0]++;
            groupMap.get(root)[1] += candy[i];
        }

        int[] dp = new int[K]; // K명 미만이므로

        for (int[] g : groupMap.values()) {
            int people = g[0];
            int candy = g[1];
            for (int j = K-1; j >= people; j--) {
                dp[j] = Math.max(dp[j], dp[j - people] + candy);
            }
        }

        int ans = 0;

        for (int i = 0; i < K; i++) {
            ans = Math.max(ans, dp[i]);
        }
        System.out.println(ans);
    }
}

 

 DSU + 배낭문제가 섞인 명작 문제이다.

핵심은 K명 미만이다 문제를 잘 확인하자

 

배낭 문제 참고!

 

https://balhae.tistory.com/256

[백준 12865번] 평범한 배낭