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

작성일 | In

문제 링크

  • http://icpc.me/18251

문제 출처

  • Good Bye, BOJ 2019 E번

사용 알고리즘

  • 스위핑
  • DFS

시간복잡도

  • $O(N log N)$

풀이

문제에 주어진 그림처럼 각 정점을 좌표 평면 상의 점으로 잡아줍시다. DFS를 이용해 정점의 깊이와 중위 순회를 이용해 쉽게 할 수 있습니다.

단순히 2차원 점들이 주어진 문제였다면 KOI 2015 중등 4번 금광처럼 $O(N^2 log N)$에 풀 수 있습니다.
하지만 이 문제에서 정점의 개수는 최대 262143이고 단순한 2차원 점이 아니라 포화이진트리 조건이 있습니다.
y좌표의 종류가 $log N$ 가지라는 것을 이용해 높이의 상/하한을 제한해주고 maximum subarray를 구해주면 $O(N log^2 N)$에 해결할 수 있습니다.
루트노드부터 스위핑하듯이 내려오면 $O(N log N)$이라는데, 저는 그냥 로그 제곱으로 풀었습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct p{
    ll x, y, w;
    bool operator < (const p &t) const {
        if(x != t.x) return x < t.x;
        return y < t.y;
    }
};

int n;
int pv;
int id[262626], arr[262626];
vector<p> v;

void dfs(int nd, int d){
    if(nd*2 <= n) dfs(nd*2, d+1);
    id[nd] = pv;
    v.push_back({d, pv++, 0});
    if(nd*2+1 <= n) dfs(nd*2+1, d+1);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n; dfs(1, 0);
    ll ans = -1e9;
    for(int i=1; i<=n; i++){
        ll t; cin >> t;
        v[id[i]].w = t;
        ans = max(ans, t);
    }
    if(ans <= 0){
        cout << ans; return 0;
    }
    ans = 0;
    for(int i=0; i<20; i++){
        for(int j=i; j<20; j++){
            ll now = 0, mx = 0;
            for(int k=0; k<n; k++){
                if(v[k].x < i || v[k].x > j) continue;
                now = max(0LL, now + v[k].w);
                mx = max(mx, now);
            }
            ans = max(ans, mx);
        }
    }
    cout << ans;
}