백준 14244 트리 만들기

백준 14244 트리 만들기

---

이번주 부터는 dp 가 아닌 다른 알고리즘 문제를 풀어볼 까 한다. 이번 주제는 트리 이다.

n개의 노드로 이루어지고, m 개의 리프로 이루어져 있는 트리를 만들어서 그 트리의 간선들을 출력하는 것이 문제 인데, 처음에 어떻게 해결해야 할 지 몰라 혼란 스러웠다.

하지만 n-m 직전까지는 0-1, 1-2 , 2-3 이렇게 이어지다가 m개의 리프가 필요하다면 n-m 노드에 하나씩 노드들을 붙여서

0 - 1 - 2 - 3 - 4
              - 5
              - 6
              - 7
              - 8

이렇게 구현한다면, (3에 하나씩 붙은 모습이다.) 9개의 노드에 6개의 리프를 가진 트리를 만든게 되는 것임을 알 수 있었다.

이거 대로 구현하니 통과할 수 있었다. 끝!!

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, m;

    cin>>n>>m;
    for (int i = 0; i < n-1; i++)
    {
        if (i < n - m)
        {
            cout<< i << " " << i+1 <<"\n";
        }

        else
        {
            cout<< n-m << " " << i+1 << "\n";
        }
    }
    return 0;
}