[백준 / BOJ] C++ 27966 △

27966번: △

 

 

문제

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

27966번: △

 

 

풀이

문제 처음 보자마자 떠오른 생각이 별 모양 트리, 성형 트리다. 가운데 정점 하나에 모든 다른 정점들이 연결되어 있는 트리 형태로 가운데 정점으로부터 다른 모든 정점까지의 거리는 1, 이외는 모두 2인 트리다. 따라서 n - 1 + 2 * nC2 가 거리의 합이 되고, 가운데 정점을 1이라고 하면 1 2 ~ 1 n까지 모두 출력하면 된다. nC2 계산 결과가 int 범위를 초과할 수 있으므로 n의 자료형을 long long으로 해줘야 한다.

 

 

코드

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

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