이번 카카오 코테 5번 문제로 이와 유사한 문제가 출제되었다. (이진 트리이고, 범위가 작은것만 다름)
기타 레슨 문제는 블루레이의 크기를 최소한으로 해서 모든 레슨을 담는 문제다. 이 문제 또한 "전염병이 퍼질 경우에 대비해 정부에서 비축해야 하는 치료제의 개수"는 검역소로 나눠 놓은 그룹들 중에서 가장 큰 그룹의 인구수의 합이기 때문에, 가장 큰 그룹의 인구수 합이 최소가 되도록 개의 검역소를 설치할 때, 가장 큰 그룹의 인구수 합은 얼마인지를 묻는 문제가 된다.
기타 레슨 문제는 한번에 문제의 답을 구하는 해법을 찾기는 어렵지만, 만약 블루레이의 크기가 주어진다면 담을 수 있는지 여부를 찾기는 쉬웠기 때문에 이를 이용해 이분 탐색을 더해서 풀었다.
이 문제도 가능할까?
어느 두 도시도 오직 하나의 경로로만 통행할 수 있다고 했기 때문에, 문제에서 주어지는 도시들은 트리임을 알 수 있다.
트리는 재귀적인 성질을 띄고 있기 때문에 문제를 분해할 수 있더. 어떤 정점을 기준으로 자신의 자식들을 담는다고 생각할 때, 모두 담은다음에 가장 큰 것부터 끊어가는식으로 최적해를 구할 수 있다. 다음과 같이 탐욕적 선택 속성을 증명할 수 있다. 는 현재 자식을 끊어내려는 정점이고 는 자식들이다.
우선 담을 수 있다면 최대한 담는것이 이득이라는 것을 증명해보자. 만약 어떤 최적해가 최대한 담지 않는 방식으로 위와 같이 만들어졌다고 가정해보자. 가 속한 그룹은 사실 과 를 모두 담을 수 있지만 끊어놨다.
끊어놓은 것을 그냥 잇는 해로 바꾸더라도 는 줄어들기 때문에 무조건 이득이다.
그렇다면 가장 큰 것부터 끊어주는 것이 최적해라는 것은 어떻게 증명할 수 있을까?
마찬가지로 어떤 최적해가 큰 것부터 끊어주는 것이 아닌 방식으로 만들어졌다고 하자.
보다 가 속하는 그룹의 인구수가 더 크지만 을 끊어주었다. 이렇게 선택했는데 최적해였다고 하자
그 최적해를 이와같이 더 작은 쪽을 포함하게 바꿀 수 있다.
가 속한 그룹은 원래의 답보다 인구수가 작아지므로 으로 바꿀 수 있고, 또한 마찬가지다.
이렇게 답을 바꾸더라도 절대로 손해를 보지는 않는다.
public class Main {
static int[] S; static long M;
static ArrayList<ArrayList<Integer>> adj;
static int cnt;
// here 루트로 하는 트리를 정점의 가중치의 합이 M을 넘지 않게
// 최적의 방법으로 나누고 here이 속한 그룹의 가중치의 합을 반환
static long postorder(int here, int parent) {
long sum = S[here];
PriorityQueue<Long> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int there : adj.get(here)) {
if (there == parent) continue;
long t = postorder(there, here);
sum += t; pq.offer(t);
}
// 어차피 끊어내야 한다면 큰거부터 끊어낸다
while (!pq.isEmpty() && sum > M) { sum -= pq.poll(); cnt++; }
return sum;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder ans = new StringBuilder();
int TC = Integer.parseInt(br.readLine());
while (TC-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
S = new int[N + 1];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 1; i <= N; i++) S[i] = Integer.parseInt(st.nextToken());
adj = new ArrayList<>(N);
for (int i = 0; i <= N; i++) adj.add(new ArrayList<>());
for (int i = 0; i < N - 1; i++) {
st = new StringTokenizer(br.readLine(), " ");
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
adj.get(u).add(v); adj.get(v).add(u);
}
// f(x) = 한 그룹의 가중치의 합이 x가 넘지 않게,
// 최적의 방법으로 잘랐을 때 자르는 횟수가 K를 넘지 않게 자를 수 있는지 여부
// f(lo) = false f(hi) = true인 hi를 반환
long lo = 0; long hi = 100000000000000L;
int max = 0;
for (int i = 1; i <= N; i++) max = Math.max(max, S[i]);
while (lo + 1 < hi) {
long mid = (lo + hi) / 2;
M = mid; cnt = 0;
postorder(1, 1);
if (max <= mid && cnt <= K) hi = mid;
else lo = mid;
}
ans.append(hi).append("\n");
}
System.out.print(ans);
}
}
트리의 순회 과정은 정확하게 정점을 한 번씩만 방문하기 때문에 총 번을 방문하게 되고, 인접 간선은 번 검사하고 검사할 때 마다 의 우선순위큐에 대한 삽입이 이루어진다. 끊어내는 과정 또한 아무리 많이 끊어봐야 간선의 개수보다 많이 끊을 순 없다.
이분 탐색의 상한은 이므로