백준 8987 수족관 3 (KOI 2013 고등부 4)

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

8987번: 수족관 3

 

이 문제는 주변에서 웰노운처럼 말하길래 한 번 풀어봤다. 심지어 solved.ac 클래스 문제이다. 그리고 KOI 문제들은 보통 좋은 퀄리티를 보여주기 때문에 풀어보기도 했다.

 

우선 문제에서 트리를 모델링할 수 있다. 높이가 높은 수평선 순서대로 트리 노드를 만들어주고 노드에 직사각형 넓이를 부여해준다. 그리고 수평선 아래로는 물이 생길 수 없으니까 수평선을 기준으로 왼쪽 오른쪽을 나눠서 다시 작업을 해준다. 카르테시안 트리라고도 부른다.

이와 비슷하게 트리를 모델링하는 문제로는 JOISC constellation 3이 있다. (https://www.acmicpc.net/problem/18845)

 

이제 한 수평선에 구멍을 뚫는다는 것은 어떤 정점으로부터 루트까지의 경로에 있는 정점의 물을 뺀다는 것이다.

자명하게 리프 노드에서 구멍을 뚫는 것이 리프 노드가 아닌 노드에서 구멍을 뚫는 것보다 좋다.

 

이제 문제는 정점 $N$개의 트리가 주어졌을 때, 리프 정점 $K$개를 선택해서 정점부터 간선까지에 색칠을 한다고 했을 때 색칠된 노드에 있는 수의 총합을 최대화 하는 문제로 바뀌었다.

 

이것은 두 가지 방법으로 풀 수 있다.

 

첫번째 방법은 슬로프 트릭을 사용하는 것이다.

$dp1_{i, j}=i$번 정점의 서브트리에 대해서 $j$개의 리프 노드를 선택해서 각각 정점부터 $i$번 노드까지 색칠한다고 했을 때 (정점부터 루트까지 아님!) 색칠된 노드의 수 총합의 최댓값이라고 하자

그리고 $dp2_{i, j}=dp1_{i, j}-dp1_{i, j-1}$이라고 하자. $dp1_{i, 0}=0$이다.

$dp2_{i, j} \leq dp2_{i, j-1}$임은 tree dp를 할 때 자식의 서브트리 dp를 합치는 과정에서 알 수 있다. 좀 더 자세히 말하자면 자식들의 $dp2$가 단조성을 띄고 있다면 자식들의 $dp2$를 모아서 정렬한 뒤에 $dp2_{i, 1}$에 $i$번 정점의 값을 더해준다면 $i$번 정점의 $dp2$값을 알 수 있다는 것이다.

이것을 merge sort 하듯이 하면 $O(N^2)$에 할 수 있다. 여기에 small to large technique를 사용해서 priority_queue로 $dp2$를 관리해주면 $O(Nlog^2N)$에 문제를 풀 수 있게 된다.

 

두번째 방법은 많이 알려진 방법인데, 그리디하게 현재 선택했을 때 색칠되는 노드의 값의 합이 가장 큰 노드를 계속 선택한다는 것이다. 어떤 노드를 선택했을 때 색칠되는 노드의 값의 합과 현재 노드로부터 안 색칠되어있는 가장 높은 조상 노드를 lazy segment tree로 관리할 수 있다. 따라서 문제를 $O(NlogN)$에 풀 수 있다.

그리디한 방법이 작동하는 이유는 mcmf 모델링을 통해서 해결할 수 있다.

트리의 간선을 따라서 아래쪽으로 capacity가 1이고 cost가 (-자식 노드의 값)을 가지는 간선과 capacity가 inf이고 cost가 0인 간선을 만들어준다. mcmf의 작동하는 방법이 최단거리를 계속 구해서 그 방향으로 flow를 흘려준다는 것인데, 이는 위에서 그리디하게 색칠하는 정점의 값의 합이 최대인 리프 노드를 계속 선택해준다는 방법과 일치하기 때문에 그리디가 성립한다.