[백준_14244] 트리만들기

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

14244번: 트리 만들기

트리만들기.

이번 하반기 카카오 블라인드 공채 4번문제도 트리문제이기도 했고  
그래프탐색과달리 트리문제에는 약한것 같아서 이 위주로 풀어보려고 한다.

트리문제라던데 이 풀이가 맞나? 싶으면서 푼 문제.

난이도는 실버이지만 풀이가 다양해 재밌어 보이기도하고 독특해서 들고왔다.

 

풀이 :

n은 node, m은 리프노드 갯수로 주어지는데 트리의 소소한 특성정도만 알면 '구현력'으로 풀 수 있는 문제같다.
이 문제의 핵심은 'm이 2보다 크고, 2보다 하나씩 커질때마다(3, 4, 5...) 중간에 가지를 한개씩 더 추가를 해주어야 한다'
가 이 문제의 핵심이었다. 
n==4, m==3으로 예를 들었을때 (0,1) , (1,2) , (1,3) 과 같이 1을 기준으로 노드가4개 리프노드가 3개인 것을 만들 수 있지만
(0,1) , (0,2) , (0,3)인 모양도 노드가 4개 리프노드가 3개임을 충족시킬 수 있다. 
그래서 m == 2 일때와 아닐때로 나눈 후 1부터 n-1까지의 for문을 통해 시작점인 now_node의 위치(값)를 변경하는 형태로 코드를 짜보았다.

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

now_node=0
count = m-1
for i in range(1,n):
    if m==2:
        print(now_node,i)
        now_node+=1
    else:
        print(now_node,i)
        now_node+=1
        if count:
            now_node-=1
            count-=1

 

아래 블로그에는 내 풀이와 또 다른 2가지 풀이가 실려있으니 여러 풀이법을 보고 싶으신 분들은 참고하면 좋을 것 같다.

https://tarra.tistory.com/entry/%EB%B0%B1%EC%A4%80-14244%EB%B2%88-%ED%8A%B8%EB%A6%AC-%EB%A7%8C%EB%93%A4%EA%B8%B0-python