[백준/18251] 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) (Python)

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

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

 

Difficulty : Platinum 4

 

Status : Solved

 

Time : 00:39:26

 

---

 

문제 설명

 

 

욱제는 🎄포화이진트리🎄를 종이에 그렸다. 노드에 정수 가중치도 채워 넣었다. 욱제는 적당한 직사각형 영역을 잡아서, 영역 내에 있는 노드들의 가중치 합을 최대로 하고 싶다. 직사각형은 하나 이상의 노드를 포함해야 하고 직사각형은 비뚤어지면 안 된다.

 

 

문제에서 생략된 정의는 다음과 같다. 이해가 안 되면 읽어보자.

 

1. 직사각형은 축에 평행하며, 변이 노드에 걸치면 안 된다.
2. 모든 노드 u에 대해, u의 왼쪽 서브 트리에 속하는 모든 노드의 x좌표는, u의 x좌표보다 작다.
3. 모든 노드 u에 대해, u의 오른쪽 서브 트리에 속하는 모든 노드의 x좌표는, u의 x좌표보다 크다.
4. 자식 노드의 y좌표는 부모 노드의 y좌표보다 작다.
5. 트리에서의 깊이가 같은 노드의 y좌표는 모두 같다.

 

 

입력 및 출력

 

입력

 

첫째 줄에 노드 개수 N이 주어진다. (1 ≤ N ≤ 262,143, N은 2^k-1 꼴의 자연수)
둘째 줄에 노드의 가중치 Wi가 노드 번호 순서대로 주어진다. (-10^9 ≤ Wi ≤ 10^9)
루트 노드의 번호는 1이고, i번 노드의 좌우 자식 노드의 번호는 각각 2×i, 2×i+1이다.

 

출력

 

욱제가 얻을 수 있는 가중치의 최대 합을 출력한다.

 

입력 예시

 

15
-2 8 -3 -9 0 -6 3 4 -1 10 -1 7 -100 7 -1

 

출력 예시

 

24

 

 

---

 

풀이

 

 

잘 생각해 보면, 직사각형의 y축은 depth의 차가 된다. 즉 depth 구간 내에 속하는 모든 가중치에 대해, 가중치 연속 부분합의 최대를 구하는 문제로 볼 수 있겠다. 이는 O(N)의 시간복잡도가 소요된다. (카데인 알고리즘. DP 문제의 일종으로 볼 수 있으며 O(N)시간 내에 모두 풀이할 수 있겠다)

 

또한 아주 감사하게도 포화 이진트리의 형태이므로, 이 트리의 depth는 logN의 범위를 가진다. 즉 O((logN)^2)의 탐색을 통하여 모든 구간 내에서의 연속 부분합을 전부 탐색해 볼 수 있고, 그 중 최댓값이 문제에서 요구하는 정답이 된다. (이거 왜 A번이라고 생각하신거죠..)

 

최종적으로 O(N(logN)^2)의 시간복잡도 내에 문제를 풀이할 수 있겠다.

 

p.s. 문제에서 주어지는 가중치 리스트는 y축 - x축 순서로 배열되어 있으므로, 이를 적당히 가공해줄 필요가 있다.

 

p.s.2. 어떻게 DFS로 푸는지는 아직도 감이 잘 오지 않는다... 출제자의 의도가 궁금하다

 

풀이 코드

N = int(input())
num_list = list(map(int, input().split()))
ans = -float('inf')
depth_list = [0]*N


def div_and_con(start, end, depth) :
  mid = (start + end) // 2
  depth_list[mid] = depth
  if start == end :
    return 
  div_and_con(start, mid-1, depth+1)
  div_and_con(mid+1, end, depth+1)

def maximum_subquery(mindepth, maxdepth) :
  global ans
  result = None
  for i in range(N) :
    if not mindepth <= depth_list[i] <= maxdepth :
      continue
    if result is None :
      result = num_list[i]
    else :
      result = max(result + num_list[i], num_list[i])
  ans = max(ans, result)

div_and_con(0, N-1, 0)
maxdepth = max(depth_list)
for i in range(maxdepth) :
  for j in range(i+1, maxdepth+1)

 

풀이 완료!