알고리즘||코딩테스트/백준
14244번 트리 만들기 (Silver4)
째로스
2023. 6. 23. 14:52
https://www.acmicpc.net/problem/14244
14244번: 트리 만들기
n과 m이 주어졌을 때, n개의 노드로 이루어져 있고, m개의 리프로 이루어져 있는 트리를 만드는 프로그램을 작성하시오. 항상 정답이 존재하는 경우만 입력으로 주어진다. 트리는 사이클이 없는
www.acmicpc.net
import sys
n,m=map(int,sys.stdin.readline().split())
print(0,1)
for i in range(1,n-m+1):
print(i,i+1)
if m!=2:
for i in range(n-m+2,n):
print(n-m,i)
m>2인 경우 0번 노드와 마지막 m-1개의 노드를 리프 노드로 만들면 된다.
예로 n=6, m=4일 때, 0번 노드가 하나의 리프노드이므로 2개의 중간 노드를 두고
나머지 3,4,5 번 노드를 리프노드로 만들면 된다. (0번 노드도 리프 노드 임에 유의한다.)
m==2인 경우는 양 끝 노드가 리프 노드가 되는 경우이므로 한줄로 이어붙이면 된다.
