🐨BOJ#14244]트리 만들기(Python)

14244번: 트리 만들기

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

www.acmicpc.net

문제를 이해하기 위해 그래프를 그리는 곳에 입력해 예제 출력을 각각 넣어 보았다.

그림을 보면 리프는 무조건 2개 이상 생긴다. 그리고 루트를 어느 것으로 정하느냐에 따라 트리의 모양이 바뀔 수 있다.

n, m = map(int,input().split())
cnt = 0
for i in range(n-1):
    print(cnt,i+1)
    if n-m>cnt:
        cnt+=1

n-m까지만 직선노드를 증가시키면 해결!

나머지는 모두 마지막 부모 노드에 리프로 달아준다.

붉은 각설탕