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 을 살..
2022. 9. 5.
