BOJ 4002: 닌자배치

Link

• https://www.acmicpc.net/problem/4002

• APIO 2010 1번

Tag

• 트리

• 오일러 투어 테크닉

• 세그먼트 트리

Time Complexity

• $O(NlgN)$

트리 형태로 닌자 조직이 주어진다. 각각의 닌자는 받아야 하는 월급, 리더십 레벨 속성을 가지고 있다.
우리는 '매니저' 닌자를 선택해, 매니저를 루트로 하는 서브트리에서 닌자들을 선택할 수 있다. 선택된 닌자들의 월급의 합은 $M$ 이하가 되어야 한다. 이때 (매니저의 리더십 레벨) * (선택된 닌자들의 수) 를 최대화 해야 한다. 임의의 매니저를 정했으면, 그리디하게 월급이 적은 닌자들부터 선택하는게 최적이다.

나이브하게 모든 닌자들을 매니저로 시도해보면서, 서브트리의 닌자들 중 월급이 작은 순서대로 정렬 후 $M$ 이하일 때 까지 최소를 고르면 $O(N^{2}lgN)$ 이다. 이것을 최적화 한다. 자식 노드에서 선택되지 못한 닌자를 부모노드에서 선택할 이유는 없다. 따라서 재귀적으로 자식 노드부터 해결한 후, 부모단에서 합쳐주면 된다. 자식 노드들에서 $M$ 이하가 되도록 잘 고르고, 부모단에서 모두 합하자. 그 합이 $M$ 초과라면 선택된 닌자들 중 월급이 가장 큰 닌자를 제외시키면 된다. 위 작업은 오일러 투어 테크닉으로 세그먼트 트리를 구성해 RMQ를 날리면 된다. 최댓값을 찾고, 해당 값을 -1로 업데이트한다. 이는 해당 닌자를 제외시킨다는 의미이다. 자식 노드 단계에서 제대로 해결했다면, 세그먼트 트리에는 선택된 닌자들의 월급만 남아있을 것이다.