[백준 - Python] 14244. 트리 만들기

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

 

코드

n, m = map(int, input().split())

cnt = 0
for i in range(n-1):
    print(cnt, i+1)    # cnt가 n-m 이상이면 cnt는 그대로 유지가 되므로, 리프 노드에 노드들을 이어붙일 수 있게 됨
    if n-m > cnt:
        cnt += 1

 

접근 방법

- 연결을 어떤 식으로 하든, 리프 노드는 최소 2개 이상이다.

- n개의 노드 중에서 m개의 노드가 리프 노드이면, n-m개의 노드가 리프 노드가 아니다.

- n-m번은 순차적으로 연결을 해주고, 그 이후 연결은 마지막 노드에 전부 연결해 준다.

 

배운 점

- 트리의 최소 리프 노드 개수를 토대로, 어떠한 방식으로 리프 노드를 만들어 나갈지 생각해봐야 했던 문제