본문 바로가기

정상적인 풀이

백준 27092 - 생물 연구

 문제를 요약하자면, 크기가 2 이상이면서 동일한 높이이며, 최소 공통 조상이 전부 동일한 정점의 집합의 개수를 세는 것이다. 정해를 읽어봤는데 생각과는 달라서 작성하게 되었다.

 

 우선, 제곱 풀이를 생각해볼 수 있다. tree dp를 돌리면서, 어떤 서브트리의 루트를 최소 공통 조상으로 하는 집합의 개수를 세는 것이다. 만약 각 서브트리가 특정한 깊이를 가진 정점의 개수를 들고 있다면, 한 서브트리에서 문제의 답에 더해주어야 할 것은 각 높이에 대해, 각 서브트리가 가진 정점의 개수를 전부 곱한 값(그 높이의 정점이 존재하는 서브트리가 2개 이상인 경우에 한하여)을 전부 더해주면 된다는 사실을 직관적으로 알 수 있다.

 다음과 같은 경우에, 1번 정점을 기준으로 카운팅해보자. 2번 정점을 루트로 하는 서브트리에는 깊이가 1인 정점이 1개, 2인 정점이 2개 있고, 이것을 편의상 (1,2)로 표현하자. 그렇다면 3번 정점을 루트로 하는 서브트리에는 (1,3,2)라는 튜플이 대응된다. 그렇다면 답은 깊이가 1인 것들의 묶음을 세기 위해 (1+1)*(1+1)-1-1-1이 되는데, 그 이유는 정점을 단 하나만 고르는 경우를 제외해야 하기 때문이다. 같은 원리로 깊이가 2인 정점들의 집합 개수를 세기 위해서는 (2+1)*(3+1)-2-3-1이 된다. 깊이가 3인 것은 그러한 서브트리가 단 하나뿐이므로 세지 않는다. 이러한 방식을 적용하며 답을 계산하면 O(n^2)에 문제가 해결된다.

 

 그렇다면 이 풀이를 어떻게 문제가 해결될 수 있는 시간 안에 돌도록 시간복잡도를 개선할 수 있을까? 답은 small to large trick에 있다. 이 트릭을 간단히 설명하자면, 특정한 집합을 합칠 때 가장 큰 집합에 다른 집합들을 합쳐주는 방식으로 큰 집합의 원소들이 움직이는 것을 피하는 것만으로도 그 합치는 횟수가 O(nlogn)이 된다는 사실을 활용하는 것인데, 이것에 대해서는 타 블로그 참고를 권한다. 아무튼, 이 문제에 적용하려면 각 서브트리마다 가장 깊은 정점이 존재하는 서브트리에 다른 서브트리의 각 높이별 정점 개수 테이블을 합쳐주는 것을 해주면 된다. 원래는 그렇게 답을 합쳤을 때 집합의 크기가 다른 집합의 크기만큼 늘어나는 것이 일반적이겠지만, 이 문제에서는 그마저도 1밖에 안 늘어나기 때문에 걱정할 이유가 없다. 이러한 방식을 적용하면 문제가 해결되며, 그 시간복잡도는 O(nlogn)이다.

 

 

p.s. 정해와 같다고 한다.

'정상적인 풀이' 카테고리의 다른 글

JOI 2022 리뷰  (0) 2023.07.20
COI 2017 리뷰  (0) 2023.07.18
백준 7936 - N의 존재  (1) 2022.12.20