[BOJ 14244 // C++] 트리 만들기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 14244번 문제인 트리 만들기이다.
문제는 아래 링크를 확인하자.

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

14244번: 트리 만들기

 

$n$이 3 이상인 트리에는 항상 degree가 2 이상인 노드(즉, 리프가 아닌 노드)가 존재한다. 따라서 0번 노드가 리프가 아니라고 가정해도 문제의 조건을 만족하는 트리를 항상 찾을 수 있다.

 

이제 1번부터 $m$번 노드를 각각 0번 노드와 연결해 리프로 삼고, $m+1$번 이상 번호의 노드는 기존 리프노드와 연결하는 것으로 총 리프의 수를 유지하면 문제의 조건을 만족하는 트리를 항상 얻을 수 있다. 주어진 조건에 따라 $m$은 $n-1$ 이하이므로 위와 같은 트리 구성이 항상 가능함을 확인하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N, M;

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

	cin >> N >> M;
	for (int m = 1; m <= M; m++) cout << 0 << ' ' << m << '\n';
	for (int i = M + 1; i < N; i++) cout << i - 1 << ' ' << i << '\n';
}