[백준] 14244- 트리 만들기 (S4)

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

14244번: 트리 만들기

난이도는 쉽지 않아보이는데 의외로 쉽다.

알고리즘 분류에 나와있듯 트리를 이용한 구성적인 문제다.

트리가 어떻게 구성되는지 일반화 될 수 있는 규칙을 찾아 문제를 풀면 된다.

 

문제 조건에 의해 리프노드는 항상 최소 2개이고, 답이 항상 존재한다.

리프노드가 2개인 경우는 딱 한가지다. 모든 노드가 일직선으로 연결되면 된다.

 

리프노드가 3개 이상인 경우는 하나의 중심 노드에 대해 리프노드를 3개 만들면 된다.

더 간단하게 생각하면, 일단 중심 노드에 대해 리프노드가 존재할 가지 3개를 만들어두고,

남는 노드들은 가지에 계속 일직선으로 이어붙여서 리프노드 개수가 늘어나지 않도록 유지해주면 된다.

 

리프노드가 2개인 경우가 코너케이스인 점을 고려하여 위 내용을 구현하면 된다.

리프노드가 3개 이상이라 하나의 중심노드에 리프노드가 붙는 경우, 중심노드는 리프로서 세지 않지만,

리프노드가 2개인 경우 중심노드에 가지하나만 뻗어서 계속 붙인다고 생각하여

중심노드도 리프로서 포함하면 구현이 편해진다.

 

n, m = map(int, input().split())
leaf = 0
if m == 2:
    leaf = 1 # 중심 노드를 리프로 포함
    
last_leaf = 0
for i in range(1, n):
    if m > leaf:
        print(0, i)
        leaf += 1
    else:
        print(last_leaf, i)
    last_leaf = i