백준/실버

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

게임개발기원 2023. 6. 6. 17:21

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

 

14244번: 트리 만들기

n과 m이 주어졌을 때, n개의 노드로 이루어져 있고, m개의 리프로 이루어져 있는 트리를 만드는 프로그램을 작성하시오. 항상 정답이 존재하는 경우만 입력으로 주어진다. 트리는 사이클이 없는

www.acmicpc.net

#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개를 제외한 나머지 리프노드를 트리의 맨 밑바닥에 전부 만드는 형태이다.