BOJ 18251: 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy)

Link

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

• Good Bye, BOJ 2019! E번

Tag

• 완전탐색

Time Complexity

• $O(Nlg^{2}N)$

 각 정점에 가중치가 있는 포화이진트리를 평면에 그려서 x, y축에 평행한 임의의 직사각형 내부 가중치의  합을 최대화해야한다. 금광 하위호환...?

 그냥 완전탐색 하면 된다. 포화이진트리에 노드가 $N$개면 높이가 $lgN$이고, 이는 직사각형의 위아래가 될 수 있는 경우의 수가 $lg^{2}N$ 밖에 없음을 의미한다. 이 모든 후보에 대해 $O(N)$에 최대 연속합을 구해주면 된다. 

Code