[백준 14244번] 트리 만들기 (C++)

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

14244번: 트리 만들기

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

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

    int N, M;
    cin >> N >> M;

    for(int i=0; i<N-M; i++) //일직선
    {
        cout << i<< " " << i+1 << "\n";
    }

    for(int i=N-M; i<N-1; i++)
    {
        cout << N-M << " " <<i+1 <<"\n";
    }

    return 0;
}

N-M까지는 일직선으로 쭉 그어준다.

트리가 일직선인 경우에는 리프노드가 2개이다 (맨앞, 맨뒤)

 

현재 N-M이 끝 점이므로, 여기서 부터 간선을 추가하여 리프노드를 만들어준다.

맨 위에 리프노드 1개를 제외한 나머지 리프노드를 트리의 맨 밑바닥에 전부 만드는 형태이다.