[백준] 20303번 : 할로윈의 양아치 (Java)

문제 링크

20303번: 할로윈의 양아치

---

이번에는 두가지 알고리즘을 합친 혼종 문제를 풀어보겠습니다..

이번 문제는 반은 맞고 반은 다른 분의 블로그를 참고해서 풀었습니다,,

언젠가는 대부분의 문제를 저 혼자서 풀 날이 오겠죠??? 그 때를 기다리며 오늘도 열심히 달려보겠습니다~

풀이

분리 집합(유니온-파인드) + 배낭 문제 풀이로 풀었습니다.

저도 처음에  배낭 문제가 아니라, 그저 분리 집합으로 연결된 아이들 중 최대의 사탕 개수를 구하면 될 줄 알았는데,

알고보니 모든 조합을 구하면 시간초과가 나는 문제였습니다.

마침 사탕(배낭문제에서의 가치)과 공명하기위한 최소 아이의 수(배낭문제에서의 무게)가 배낭 문제의 조건과 일치하기 때문에, 배낭 문제로 이 문제를 해결해야 했습니다.

하지만 저는 배낭 문제를 푼 지 세 달이 지났기 때문에 배낭문제는 다른 블로그의 풀이를 참고하여 풀었습니다.

풀이 과정은 다음과 같습니다.

1. 친구 관계인 아이들을 분리 집합으로 묶어줍니다.
2. 묶은 아이들 = 하나의 집합으로 보고, 집합 안에 있는 아이들의 수와 사탕의 합계를 구해 저장해둡니다.
3. 저장해둔 아이들의 수와 사탕의 합계 정보를 토대로 배낭 문제 알고리즘으로 최대의 사탕 수를 구합니다.

풀이코드

import java.io.*;
import java.util.*;
import java.util.stream.IntStream;

class Main {

    static int n, m, k;
    static int[] parent;
    static int[] candy;

    private static void solve(BufferedReader br) throws IOException {
        int[] inp = Arrays.stream(br.readLine().split(" "))
            .mapToInt(Integer::parseInt).toArray();
        n = inp[0]; m = inp[1]; k = inp[2];
        candy = Arrays.stream(("0 " + br.readLine()).split(" "))
            .mapToInt(Integer::parseInt).toArray();

        parent = new int[n + 1];
        IntStream.range(1, n + 1).forEach(i -> parent[i] = i);

        while (m-- > 0) {
            int[] line = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();
            uniParent(line[0], line[1]);
        }

        int[] cnt = new int[n + 1];
        Arrays.fill(cnt, 1);
        for (int i = 1; i <= n; i++) {
            if (parent[i] == i) continue;
            int p = getParent(i);
            candy[p] += candy[i];
            cnt[p] += cnt[i];
        }

        int[] dp = new int[3001];
        for (int i = 1; i <= n; i++) {
            if (parent[i] != i) continue;
            for (int j = k - 1; j - cnt[i] >= 0; j--) {
                dp[j] = Math.max(dp[j], dp[j - cnt[i]] + candy[i]);
            }
        }
        res.append(dp[k - 1]);
    }

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

    static void uniParent(int a, int b) {
        a = getParent(a);
        b = getParent(b);

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

    private static StringBuilder res;
    public static void main(String args[]) throws Exception {
        if (args.length > 1) fileInputOutput(args[0], args[1]);
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            res = new StringBuilder();
            solve(br);
            bw.write(res.toString());
        }
    }

    private static void fileInputOutput(String inputPath, String outputPath) throws IOException {
        System.setIn(new FileInputStream(inputPath));
        System.setOut(
            new PrintStream(
                new BufferedOutputStream(
                    new FileOutputStream(outputPath)
                )));
    }
}

 

배운점

• 분리 집합(유니온-파인드)을 복습할 수 있었습니다.
• 배낭 문제를 복습할 수 있었습니다.

---

부족한 글 봐주셔서 감사합니다. 🙇

풀이와 코드에 부족한 점이나 추가하면 좋을 점이 있으면 댓글 주세요!