[BOJ 27966] △

모든 정점 쌍에 대해 두 정점 사이의 거리의 합을 최소화하는 문제이다. 머릿속으로 모양 몇 개를 떠올리면 금방 풀 수 있는 문제이다. 하나의 정점 아래에 다른 모든 정점을 연결하면 된다. 

 

이렇게 한다면 최솟값은 루트 정점에서 다른 정점들 사이의 거리의 합인 $1\times N-1$과 다른 모든 정점 쌍들 사이의 거리의 합인 $2\times\ _NC_2$를 더한 값이 된다. int 범위를 벗어남을 유의하자.

long long N;
int main(void) {
    fastio;
    cin >> N;
    cout << N - 1 + (N - 1) * (N - 2) << "\n";
    for (int i = 2; i <= N; i++) {
        cout << 1 << " " << i << "\n";
    }
    return 0;
}