[백준] BOJ_20303 - 할로윈의 양아치

이종찬·2026년 2월 3일
baekjoon
post-thumbnail

1. 문제 정보

  • 문제 요약: 아이들 간의 친구 관계가 주어집니다. 한 아이의 사탕을 뺏으면 그 친구들의 사탕까지 전부 뺏게 됩니다(연대 책임). 어른들에게 들키지 않으려면 울음소리가 KK 미만이어야 합니다. 이때 뺏을 수 있는 사탕의 최대 개수를 구하는 문제입니다.
    • 아이 한 명의 울음소리 크기는 1입니다. (즉, 뺏은 아이들의 총인원수가 KK보다 작아야 합니다.)
  • 난이도: Gold 3
  • 링크: 백준 20303번 - 할로윈의 양아치

2. 접근 방식

1) 문제의 본질: 그룹화와 자원 배분

이 문제는 두 단계로 나뉩니다.

  1. 친구 관계 파악: 친구끼리는 무조건 운명 공동체입니다. 따라서 이들을 하나의 '그룹'으로 묶어야 합니다.
  2. 최적의 선택: 각 그룹을 선택하면 그룹 인원수(무게)만큼의 비용이 들고, 그룹 사탕 총합(가치)만큼의 이득을 얻습니다. 제한된 용량(K−1K-1) 내에서 가치를 최대화해야 합니다.

즉, 이 문제는 Disjoint Set(분리 집합)으로 데이터를 전처리한 후, 0/1 Knapsack(배낭 문제)으로 해결하는 복합 유형입니다.

2) 알고리즘 설계: Union-Find & Knapsack

  • Union-Find (최적화 포인트): 단순히 연결 여부만 저장하는 것이 아니라, union 연산을 수행할 때 해당 그룹의 크기(인원수)와 가치(사탕 수)를 루트 노드에 몰아서 합쳐줍니다. 이렇게 하면 나중에 별도로 그룹을 순회하며 합계를 구할 필요 없이, O(1)O(1)에 그룹 정보를 획득할 수 있습니다.
  • Knapsack DP: 각 그룹(루트 노드)을 하나의 '물건'으로 간주합니다.
    • 무게(WW): 그룹 내 인원수
    • 가치(VV): 그룹 내 사탕 총합
    • 제한(LimitLimit): K−1K - 1 (문제 조건이 KK 미만이므로)

3) 점화식

DP[j]DP[j]를 '현재까지 고려한 그룹들로 인원수 jj명을 채웠을 때 얻을 수 있는 최대 사탕 수'라고 정의합니다.

DP[j]=max⁡(DP[j], DP[j−CurrentGroupSize]+CurrentCandySum)DP[j] = \max(DP[j], \ DP[j - \text{CurrentGroupSize}] + \text{CurrentCandySum})

이때, 1차원 배열로 공간 복잡도를 최적화하려면, 중복 선택을 방지하기 위해 인덱스를 큰 수에서 작은 수(K−1→WK-1 \rightarrow W)로 역순 순회해야 합니다.

3. 코드 구현

1) 초기 접근 (Map 사용)

처음에는 Union-Find 후 Map을 이용해 그룹별 리스트를 만들고 다시 순회하는 방식을 사용했습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N, M, K;
    static int[] child, parent;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        child = new int[N + 1];
        parent = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            child[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, List<Integer>> map = new HashMap<>();
        for (int i = 1; i <= N; i++) {
            int crew = find(i);
            List<Integer> candies = map.getOrDefault(crew, new ArrayList<>());
            candies.add(child[i]);
            map.put(crew, candies);
        }

        int[] dp = new int[K];
        for (int key : map.keySet()) {
            int count = 0;
            int sum = 0;
            for (int candy : map.get(key)) {
                sum += candy;
                count += 1;
            }

            if (count >= K)
                continue;

            // Knapsack Logic
            for (int i = K - 1; i >= count; i--) {
                dp[i] = Math.max(dp[i], dp[i - count] + sum);
            }
        }

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

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

        if (a < b) {
            parent[b] = a;
        } else {
            parent[a] = b;
        }
    }

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

2) 최적화 코드 (Union 시 데이터 병합)

union 연산 시점에 인원수(group)와 사탕 합(sum)을 루트 노드에 합치는 방식입니다. Map 같은 별도 자료구조 없이 배열만으로 깔끔하게 해결됩니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N, M, K;
    static int[] child, parent, sum, group;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        child = new int[N + 1];
        parent = new int[N + 1];
        sum = new int[N + 1];
        group = new int[N + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            child[i] = Integer.parseInt(st.nextToken());
            parent[i] = i;
            group[i] = 1;        // 초기 그룹 크기는 1 (자기 자신)
            sum[i] = child[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);
        }

        // DP[j]: 인원 j명일 때 최대 사탕 수
        // K 미만이어야 하므로 배열 크기는 K (인덱스 0 ~ K-1)
        int[] dp = new int[K]; 
        
        for (int i = 1; i <= N; i++) {
            // 루트 노드가 아니면 스킵 (이미 루트에 합쳐짐)
            if (parent[i] != i) continue;

            // Knapsack: 중복 선택 방지를 위해 뒤에서부터 순회
            for (int j = K - 1; j >= group[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - group[i]] + sum[i]);
            }
        }

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

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

        if (a == b)
            return;

        // 작은 번호가 부모가 되도록 통일하며, 
        // **크기(group)와 사탕(sum) 정보를 부모에게 몰아줌**
        if (a < b) {
            parent[b] = a;
            group[a] += group[b];
            sum[a] += sum[b];
        } else {
            parent[a] = b;
            group[b] += group[a];
            sum[b] += sum[a];
        }
    }

    private static int find(int x) {
        if (x != parent[x]) {
            parent[x] = find(parent[x]); // Path Compression
        }
        return parent[x];
    }
}

4. 회고 및 배운 점

실패 요인 분석과 성능 개선

  • 자료구조의 선택: 첫 번째 코드에서는 HashMap<Integer, List<Integer>>를 사용하여 그룹을 관리했습니다. 이는 로직상 문제는 없지만, 데이터가 많아질수록 List 생성 및 Map 조회 비용이 발생합니다. 반면, 두 번째 코드는 Union-Find 과정에서 데이터를 병합(Aggregation)했습니다. 별도의 후처리 없이 O(1)O(1)로 그룹 정보를 갱신하므로 훨씬 효율적입니다.
  • 시간 복잡도 분석:
    • Union-Find: 경로 압축(Path Compression)을 사용했으므로 거의 선형 시간인 O(Mα(N))O(M \alpha(N))에 수렴합니다.
    • Knapsack: 그룹의 수(최대 NN) ×\times 제한 무게(KK)이므로 O(N⋅K)O(N \cdot K)입니다.
    • N=30,000,K=3,000N=30,000, K=3,000이므로 약 9×1079 \times 10^7 연산량으로, 1초 제한(Java 기준) 내에 충분히 통과 가능합니다.
profile
이종찬
왜? 라는 질문이 사라질 때까지
이전 포스트

[백준] BOJ_9084 - 동전

다음 포스트

[백준] BOJ_2482 - 색상환

0개의 댓글