[백준] 13209. 검역소 - Java

🖇️ 문제 링크

13209번: 검역소

3번 도시와 5번 도시를 잇는 도로와 4번 도시와 3번 도시를 잇는 도로에 검역소를 설치하면 치료제를 11 인분만 비축해도 된다. 1번 도시에 전염병이 발생할 경우 1번 도시와 3번 도시의 10명의 사람들이, 2번 도시에 전염병이 발생할 경우 2번 도시와 4번 도시의 11명의 사람들이, 3번 도시에 발생할 경우 10명, 4 번 도시에 발생할 경우 11명, 5번 도시에 발생할 경우 5명이 감염될 수 있으므로 어느 경우에도 11인분의 치료제로 충분히 전염병을 막을 수 있다.

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

 

---

💡 문제 분석

파라메트릭 서치로 검역소마다 limit개 이하의 치료제로 K개의 검역소를 운영할 수 있는지를 구합니다.

검역소 한 개로 운영할 수 없을 때, 큰 도시부터 하나씩 검역소를 추가합니다.

 

---

⌨️ 코드

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

public class Q13209 {
    static int N, K, cnt;
    static int[] people;
    static List<Integer>[] adj;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = stoi(br.readLine());
        while(tc-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = stoi(st.nextToken());
            K = stoi(st.nextToken());
            people = new int[N];
            adj = new ArrayList[N + 1];
            for(int i = 1 ; i<= N; i++)
                adj[i] = new ArrayList<>();

            st = new StringTokenizer(br.readLine());
            for(int i = 0; i < N; i++)
                people[i] = stoi(st.nextToken());

            for(int i = 0; i < N - 1; i++) {
                st = new StringTokenizer(br.readLine());
                int u = stoi(st.nextToken());
                int v = stoi(st.nextToken());
                adj[u].add(v);
                adj[v].add(u);
            }

            long lo = 0, hi = 0;
            for(int i = 0; i < N; i++)  {
                lo = Math.max(lo, people[i]);
                hi += people[i];
            }

            while(lo <= hi) {
                long mid = (lo + hi) / 2;
                cnt = 0;
                dfs(1, 1, mid);
                if(cnt <= K)
                    hi = mid - 1;
                else
                    lo = mid + 1;
            }

            System.out.println(hi + 1);
        }
    }

    public static long dfs(int cur, int prev, long limit) {
        Queue<Long> pq = new PriorityQueue<>(Collections.reverseOrder());
        long curPeople = people[cur - 1];
        for(int child : adj[cur])
            if(child != prev) {
                long childPeople = dfs(child, cur, limit);
                pq.add(childPeople);
                curPeople += childPeople;
            }

        while(curPeople > limit && !pq.isEmpty()) {
            curPeople -= pq.poll();
            cnt++;
        }

        return curPeople;
    }

    public static int stoi(String s) {
        return Integer.parseInt(s);
    }
}

 

---

⏱️ 결과

 

 

 

Uploaded by Notion2Tistory v1.1.0