[BOJ] 20303번: 할로윈의 양아치

문제 내용

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

20303번: 할로윈의 양아치

 

풀이 시간

1시간

풀이 과정

여러개의 그룹들을 구하는 것이어기 때문에 유니온-파인드가 떠올랐다.

이후 문제를 풀면서 최대값을 구하는 로직을 작성 해지만 오답 -> 문제를 제대로 안읽엇다.

- 여러 그룹들이어도 인원의 총 합이 K이하면 가능했다.

가능한 모든 경우의 수를 확인하기 위해 그룹들의 subset을 구하려고 했다. -> 시간초과 

 

-시간 초과의 원인

1. 그룹을 만드는 기존 코드의 시간 복잡도 => O(N^2) -> O(N)으로 줄여야 했다.

     => Map을 사용하여 구현 했다.

2. subset로직의 시간초과

    => 시간 복잡도를 줄이기 위해 Knapsack을 응용해서 풀이.

정답 코드

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


public class Main {
    static int N,M,K;
    static int[] candy;
    static int[] parent;
    static Map<Integer,int[]> group;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer 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];
        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);
        }

        group=new HashMap<>();

        for(int i=1;i<=N;i++){
            int root=find(i);

            int[] stat=group.getOrDefault(root,new int[2]);
            stat[0]++;
            stat[1]+=candy[i];

            group.put(root,stat);
        }

        int[] dp=new int[K];

        for(int x:group.keySet()){
            int[] stat=group.get(x);

            if(stat[0]>K) continue;

            for(int i=K-1;i>=stat[0];i--){
                dp[i]=Math.max(dp[i],dp[i-stat[0]]+stat[1]);
            }
        }
        int result=0;
        for(int i=0;i<K;i++){
            result=Math.max(result,dp[i]);
        }

        System.out.println(result);
    }

    static boolean union(int a,int b){
        int aRoot=find(a);
        int bRoot=find(b);

        if(aRoot==bRoot) return false;

        parent[bRoot]=aRoot;

        return true;
    }

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