[BOJ 17842] 버스노선

문제는 여기에서 확인가능하다.

---

Theorem.

$L$을 리프노드의 수라고 하면, 노선수의 최소는 $\lceil L/2 \rceil$이다.

Proof.

수학적 귀납법으로 증명이 가능하다.

 

1. 리프노드를 지웠을 때, 리프노드의 수가 유지되는 경우.

이를 만족하는 리프노드를 $x$라고 하고, 이와 인접한 노드를 $y$라고 하자. 그럼 $x$를 제거했을 때, $\lceil L/2\rceil$이 성립하고, 다시 $x$를 복구 시켰을 때, $y$에서 끝나는 경로를 $x$로 확장하면 된다.

 

2. 리프노드를 지웠을 때, 리프노드의 수가 유지되지 않는 경우.

차수가 2 이상인 $R$에 대해, 루트를 $R$로 잡고, $R$의 자식이 루트가 되는 서브트리를 두개 고른다. 그러면 리프노드가 항상 2개 이상인데, 두 리프노드를 $x$, $y$라고 하고, 이 리프노드를 트리에서 지운다. 그럼 노선의 수는 $\lceil L/2\rceil - 1$이 성립하고, $x$와 $y$를 복구하여 이 둘을 잇는 노선을 만들면 된다.

#include <bits/stdc++.h>
 
using namespace std;
 
int N, D[1000005];
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> N;
  for (int i = 0; i < N-1; i++) {
    int x, y;
    cin >> x >> y;
    D[x]++;
    D[y]++;
  }
  int r = 0;
  for (int i = 0; i < N; i++) {
    if (D[i] == 1) r++;
  }
  cout << r/2 + r%2;
  return 0;
}