BOJ 20131 : 트리 만들기

문제 링크 : https://www.acmicpc.net/problem/20131

 

관찰 1

처음 이 문제를 봤을 때 생각이 잘 안 나서, 노드 개수가 4개인 트리를 다 그려봤다.

각각의 트리에 대해 문제에서 요구하는 순열을 구했는데, 전부 다르게 나왔다.

즉, 트리가 다르면 순열이 다르다는 것을 알게 됐다.

 

관찰 2

1번 예제의 입력이 9 4 4 5 4 4 6 이었다.

4가 왜 4번 등장했는지, 9, 5, 6 은 왜 1번 등장했는지, 나머지 1, 2, 3, 7, 8 은 왜 안 등장했는지 고민했다.

예제의 트리를 그려보고 등장횟수가 같은 정점들의 공통점을 찾아봤다.

그 결과, 1, 2, 3, 7, 8 은 말단노드이기에 한 번도 등장하지 않았다는 것을 알게 되었다.

이제는 1번만 등장한 9, 5, 6 을 살펴보았고, 차수가 2인 노드라는 것을 알게 되었다.

4번 등장한 4는 차수가 5인 노드였다.

즉, 노드의 차수 = 그 노드가 등장한 횟수 + 1 이라는 사실을 발견하였다.

 

구현

차수가 1 인 말단노드들을 set 또는 max_heap 으로 관리한다.

우리가 필요한 것은 말단노드 중 최댓값이므로 max_heap 이 더 효율적일 것이다.

 

현재 순열의 값과 heap 의 top 을 연결하고, heap 의 top, 즉 말단노드는 짝을 찾았으므로 제거한다.

그 후, 짝을 하나 발견한 현재 순열의 노드의 차수를 1 줄여준다.

만약 여기서 차수가 1 이 되었다면 말단노드가 됐다는 뜻이므로 heap 에 삽입한다.

 

관찰을 통해 허들을 넘는 것이 느껴졌던, 좋은 문제였다.