문제 링크

성능 요약

메모리: 53512 KB, 시간: 528 ms

분류

자료 구조, 분리 집합, 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 배낭 문제

제출 일자

2025년 1월 19일 19:55:26

문제 설명

Trick or Treat!!

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

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

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

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

입력

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

둘째 줄에는 아이들이 받은 사탕의 수를 나타내는 정수 $c_1, c_2, \cdots, c_N$이 주어진다. ($1 \leq c_i \leq 10\ 000$)

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

출력

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

풀이

느낀점

• 골드 3~5 티어 문제에서 보통 특정 알고리즘 위주로 풀거나, 중심이 되는 고급알고리즘 + 활용할 기초 알고리즘으로 풀이가 되는데, 나름 중상급 난이도의 알고리즘 두개(union/find, 배낭)를 섞어 풀어야 해서 정말 이게 맞나 싶었다.
• 더 쉬운 방법이 있는게 아닐까 했는데 일단 풀렸다.
• union/find는 배열로 따로 빼서 관리하는게 맞는 것 같다. class안에 변수로 정의하려고 했는데 디버깅하기 어렵고 복잡해졌다.

설계 : 20분

• 그룹장 배열 int[] p와 초기 그룹목록 Group[] kids, Set realS를 선언하고 모두 자기 자신으로 초기화 한다.
• Group에는 그룹의 아이들 수와 총 사탕 개수를 기록한다.
• 관계가 입력될때마다 그룹 현황을 업데이트 한다.
  • 하위로 합쳐지는 그룹의 아이들, 사탕 수를 루트가 되는 그룹에 합친다.
  • 그룹장 배열을 변경한다. (그룹을 합친다)
  • 하위로 합쳐진 그룹을 realS에서 삭제한다.
• 실제 존재하는 그룹 realS를 아이들 수 오름차순으로 정렬하고 순회한다.
  • k명 미만으로 빼앗아야 할때, 순회중인 그룹을 포함하여 dp[]에 0~k-1명의 아이들까지 각각 빼앗을 수 있는 최대값을 업데이트 한다.

코드(Java)

• 구현 시간: 30분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 할로윈의 양아치_20303
 * Date: 2025.01.19
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
    static Group[] kids;
    static int[] p;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        int k = Integer.parseInt(input[2]);
        kids = new Group[n+1];
        p = new int[n+1];
        Set<Group> realS = new HashSet<>();

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= n; i++) {
            kids[i] = new Group(1, Integer.parseInt(st.nextToken()));
            realS.add(kids[i]);
            p[i] = i;
        }

        for (int i = 0; i < m; i++) {
            String[] rel = br.readLine().split(" ");
            int a = Integer.parseInt(rel[0]);
            int b = Integer.parseInt(rel[1]);

            int bossA = findSet(a);
            int bossB = findSet(b);

            if (bossA != bossB) {
                realS.remove(kids[bossB]);
                kids[bossA].children += kids[bossB].children;
                kids[bossA].candy += kids[bossB].candy;
                p[bossB] = bossA;
            }
        }

        List<Group> groups = new ArrayList<>(realS);
        Collections.sort(groups);

        int[] dp = new int[k];
        for (Group g : groups) {
            for (int i = k-1; i > 0; i--) {
                if (i >= g.children) dp[i] = Math.max(dp[i], dp[i - g.children] + g.candy);
            }
        }

        bw.write(String.valueOf(dp[k-1]));
		bw.flush();
		bw.close();
		br.close();
	}

    private static int findSet(int x) {
        if (p[x] == x) return x;
        return p[x] = findSet(p[x]);
    }
}

class Group implements Comparable<Group> {
    int children;
    int candy;

    Group(int children, int candy) {
        this.children = children;
        this.candy = candy;
    }

    @Override
    public int compareTo(Group o) {
        return Integer.compare(this.children, o.children);
    }

    @Override
    public String toString() {
        return children + "명 " + candy + "개";
    }
}