BOJ 28054 - Clique Partition
$K=\left\lceil N/2 \right\rceil$ 임을 유추하는 것은 어렵지 않다.
어떻게 구성해야하는지 생각해보자.
완전그래프의 간선 개수는 정점이 $V$라면 $V-1 + V-2+ \cdots + 1=\sum_{i=1}^{V-1}i=\dfrac{(V-1)V}2$ 이다.
트리 하나당 $V-1$ 개의 간선을 써야한다.
$2 \mid V$ 라면 $(V-1) \cdot (V/2) =$ 간선 개수이므로, $K=V/2$ 일 확률이 커보인다.
항상 $K=\left\lceil \dfrac{N}2 \right\rceil$ 가 위 식에서 $K$의 하한임을 알 수 있고 다음과 같은 방법으로 항상 저 $K$로 구성이 가능하다.
$N=2$ 일 때를 보면 $K=1$ 이다.
이제 $N+2$ 일 때를 구성하는 방법을 알아보자.
일단 $N+1,\ N+2$ 가 추가된다.
지금까지 있는 트리는 $N / 2$ 개 이므로 $N/2$ 개의 트리에 다음과 같이 간선을 2개씩 추가한다.
$1$번째 트리 : $(1, N+1),\ (1, N+2)$
$2$번째 트리 : $(2, N+1),\ (2, N+2)$
$\vdots$
$N/2$번째 트리 : $(N/2, N+1), (N/2, N+2)$
이제 원래 $N/2$ 개의 트리들은 모두 간선이 두 개씩 추가되어 $N+1$개가 되어서 트리이고,
새로운 트리를 하나 추가하고 다음과 같은 간선들을 삽입한다.
$(N/2+1,N+1), (N/2+1,N+2), \dots, (N, N+1), (N, N+2), \mathbf{(N+1, N+2)}$
$N/2+1 \sim N$ 까지의 노드가 모두 간선이 두개씩 들어가므로 정확히 간선이 $N$개가 추가되고 마지막에 $(N+1,N+2)$ 를 삽입해줌으로써 이 트리도 모두 union하면 안쓴 간선 없이 적절히 구성된다.
이제 $2 \mid N$일 때의 트리를 만들었으므로 $2N+1$ 의 트리를 만들어보자.
$2N$ 의 트리를 구성한다음 모든 현존하는 트리들에 $(1, 2N+1)$ 을 추가해준다음 마지막 트리는 $2N+1$ 부터 모든 노드들로 뻗어나가는 트리로 구성해주면 된다.
Comments