대회 풀이

K개의 구멍을 뚫어 가장 많은 물을 빼야한다. 아이디어는 다음과 같다.

• K=1일 때, 수평선분 중에서 구멍이 뚫린다면 뺄 수 있는 물의 양이 가장 많은 수평선분에 구멍을 뚫는 게 제일 좋다. 그 선분을 찾아 구멍을 뚫는다.
• K > 1 일 때, 제일 좋은 수평 선분에 구멍을 뚫어 물이 빠지면, 수평 선분 별로 뺄 수 있는 물의 양을 갱신해주고, 가장 좋은 구멍을 다시 찾는다. 이 일련의 작업을 K번 반복하면 된다. 이 방법은 전형적인 욕심쟁이 기법(Greedy method)이다.

이 작업을 트리를 만들어 O(N lg N)만에 해결하면 만점을 받을 수 있다. 이 작업은 수족관의 경계 모양을 반복적으로 나누어 그 정보를 트리 형태로 만들어 해결 한다. O(N^2) 시간으로 하면 48점을 받을 수 있고, O(NK) 시간으로 해결하면 84점을 받을 수 있고, O(NlogN) 시간에 해결하면 100점을 받을 수 있다.

부분문제 3번은 동적계획법(DP, Dynamic Programming)으로 해결할 수 있다. 트리의 각 노드에 대해, D[i][k] 의 값을 노드 i의 서브트리에서 k개의 구멍을 놓았을 때 뺄 수 있는 물의 최대 리터 수로 정의하여 O(NK^2)으로 풀 수 있다. 고득점을 받기 위해서는 트리를 명시적으로 구현하여야하기 때문에 고득점을 받기 쉬운 문제는 아니다.