[C++] △ (백준 27966번)

https://www.acmicpc.net/problem/27966

 

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    long long n;
    cin >> n;

    long long ans = (n - 1) + (n - 1) * (n - 2);
    cout << ans << '\n';

    for (int i = 2; i < n + 1; i++) {
        cout << 1 << ' ' << i << '\n';
    }
}

모든 정점 쌍에 대해서 두 정점 사이 거리의 합이 최소가 되도록 하기 위해서는 하나의 정점을 중심에 두고 나머지 모든 정점을 그 중심 정점에 연결하도록 트리를 구성하면 된다. 이 사실만 알면 쉽게 풀 수 있었던 문제. 아 long long으로 해야 함! (AC)