BOJ 27966 △

문제 링크입니다.

트리 이해하기

트리에서, 임의의 두 정점을 잇는 단순 경로는 유일하게 존재합니다. 이를 응용하면, 트리에서 간선으로 직접 연결된 정점 쌍을 제외하면 두 정점 사이의 거리가 1일 수 없음을 알 수 있습니다. 트리의 간선 개수는 N-1개로 고정이니, 나머지 경로들의 거리를 최소화해 봅시다.

해 구성하기

N = 3일때 트리를 구성하는 방법은 세 정점을 일직선으로 잇는 것뿐입니다.

여기에 4번째 정점을 적당히 추가해 봅시다. 가능한 경우가 세 가지 (대칭성을 고려하면 두 가지) 밖에 없으니 이를 모두 고려하면, 세 정점 중 가운데 있는 정점에 새 정점을 붙이는 게 유리합니다.

이를 일반화하면, 하나의 정점에 다른 N-1개의 정점을 모두 연결하는 게 최적이라고 생각할 수 있습니다. 가운데 정점과 다른 정점들은 간선으로 직접 연결되어 있으므로 거리가 1이고, 가운데 정점을 제외한 어떤 정점에서 가운데 정점을 거쳤다가 바로 다른 모든 정점으로 넘어갈 수 있으므로 나머지 모든 정점 쌍의 거리는 2입니다. 간선으로 직접 연결되어 있지 않은 정점 쌍 사이의 거리가 최소 2이므로, 이 트리가 실제로 최적해임을 알 수 있습니다.

이때 모든 정점 쌍에 대한 두 정점 사이 거리의 합은 $(N-1) \times 1 + {(N-1) \times (N-2) \over {2}} \times 2 = (N-1)^2$입니다.

코드

#include<bits/stdc++.h>
using namespace std;

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	long long n; cin >> n;
	cout << (n-1)*(n-1) << '\n';
	for(int i = 2; i <= n; i++) cout << "1 " << i << '\n';
}