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

문제링크 : https://www.acmicpc.net/problem/27966

27966번: △

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N;
ll dp[100001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;
    dp[0]=1;
    for(int i=0; i<100001; i++)
    {
        dp[i] = dp[i-1] + (i+1); //거리가 2인 정점 갯수 규칙
    }
    cout << (N==2 ? 1 : (N-1) + 2*dp[N-3]) << "\n"; //N=2인 경우 예외처리
    for(int i=2; i<=N; i++) cout << "1 " << i << "\n"; //성형구조이므로 1과 나머지 정점 출력
    return 0;
}

 

트리이자 애드혹인 문제이다.

사이클을 이루지 않는 한 정점끼리 가장 가까운 구조로 성형구조가 있기에 이를 기준으로 정점의 거리를 확인했다.

성형 구조는 기본적으로 정가운데 정점과 나머지는 거리가 1, 이외에는 전부 2인 거리를 갖는다.

 

거리가 1인 경우는 현재 정점을 제외한 전부이므로 N-1이 총 거리가 되게된다.

거리가 2인 경우는 따로 헤아려서 경우의 수를 구해보니 다음과 같은 규칙을 찾게되었다.

N=3 : 1
N=4 : 3
N=5 : 6
N=6 : 10

-> +2, +3, +4

 

위를 보면 증가하는 값이 1씩 증가하면서 또 이게 더해진 값이 다음값이 된다.

이에 맞게 dp식을 세워줬다.

dp[i] = dp[i-1] + (i+1);

 

이때 N은 2인 경우는 거리가 2인 경우가 없어서 따로 출력할때 예외처리를 해주었다.

이후 해당 dp식이 N=3일때부터 가정한 것이기 때문에 (N-1) + 2*dp[N-3]을 출력해주면 된다.

 

그리고 성형구조이기에 가운데 정점 1과 나머지 모두가 연결되어있다.

따라서 1과 나머지 정점들을 차례대로 출력해주면 된다.