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

문제

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

 

코드

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

public class Main{
    //N : 거리에 있는 아이들 수
    //M : 아이들의 친구 관계 수
    //K : 울음 소리가 공명하기 위한 최소 아이수
    static int N, M, K;
    static int[] candy;
    static List<List<Integer>> friends;
    static boolean[] visited;
    static List<int[]> groups;
    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());

        //한 아이의 사탕을 뺏으면 그 아이의 친구들의 사탕은 모두 뺏어버린다
        //사탕을 뺏긴 아이는 운다
        //K명의 아이가 울면 어른들이 나와버린다
        candy = new int[N + 1];
        friends = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= N; i++) {
            candy[i] = Integer.parseInt(st.nextToken());
            friends.add(new ArrayList<>());
        }
        friends.add(new ArrayList<>());
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            friends.get(a).add(b);
            friends.get(b).add(a);
        }

        //*************입력 끝**********************
        //뺏을 수 있는 사탕의 최대 개수 출력

        //그룹 만들기
        //[사람수, 사탕개수]
        groups = new ArrayList<>();
        visited = new boolean[N + 1];

        for(int i = 1; i <= N; i++) {
            makeGroup(i);
        }

        //K미만이어야 울지 않기 때문에 K보다 작아야함
        int[] dp = new int[K]; //dp[i] = 사람의 수가 i일때 가질 수 있는 사탕 최대 개수
        for(int i = 0; i < groups.size(); i++) {
            for(int j = K - 1; j >= groups.get(i)[0]; j--) {

                dp[j] = Math.max(dp[j], dp[j - groups.get(i)[0]] + groups.get(i)[1]);
            }
        }

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

    }

    static void makeGroup(int now) {
        if(visited[now]) return;
        Stack<Integer> stack = new Stack<>();
        stack.push(now);
        visited[now] = true;
        int count = 1;
        int sum = candy[now];
        while(!stack.isEmpty()) {
            int pop = stack.pop();
            for(int i : friends.get(pop)) {
                if(!visited[i]) {
                    stack.push(i);
                    visited[i] = true;
                    count++;
                    sum += candy[i];
                }
            }
        }
        groups.add(new int[]{count, sum});
    }
}

 

접근 방법

단순 그래프 문제라고 생각했는데 DP를 사용해야한다.

먼저 dfs로 연결할 수 있는 친구들만큼 묶어서 그룹을 나눠줬다.

그룹을 나눌 때 해당 그룹에 있는 인원수, 해당 아이들에게서 뺏을 수 있는 사탕의 수를 list로 저장해주었다.

그뒤는 냅색알고리즘을 적용해서 인원 = kg 사탕 = value라고 생각하고 적용 시켰다.

 

최근 모 기업 코테에 냅색 나왔는데 백퍼센트 틀렸을거 같아 속상하여 냅색 많이 푸는중...ㅠㅠ