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

제목이 뭐 이리 길어

문제는 아래와 같다.

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

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

이걸 A번으로 생각하시다니...

wookje님이 워낙 god이시긴 하지만 이럴 땐 진짜... 말잇못

 

나만 모르는 웰노운 소재가 있어서 기록해두는 문제.

---

의식의 흐름 및 해설

대체 직사각형을 어떻게 할 지 한참 고민했다.

일단 일렬로 나열된 트리노드들의 x값, y값을 어떻게 비교할지조차 한숨이 나왔다.

y값은 (1<<i)-1꼴의 번호까지 같은 높이, 즉 트리순회로 depth를 따져주면 어떻게 나올 것 같은데 x좌표가 문제였다.

 

트리를 자세히 살펴보면 가운데보다 왼쪽 노드는 무조건 x좌표가 작고, 오른쪽은 무조건 가운데보다 x좌표가 큰데, 따라서 중위 순회(inorder)를 돌아서 출력되는 순서가 x좌표 순서였다. (나만 몰랐어?)

 

이제 x좌표, y좌표도 구했으니 2차원 평면에서 스위핑하는 문제로 변했다.

x좌표 순으로 정렬해준 다음, 어차피 y좌표는 최대 18(logN)이므로 이중for문으로 y좌표 범위 내에서 x좌표 스위핑을 해주어 O(N(log^2N))에 답을 구해주면 된다.

 

사실 처음에는 좌표평면에 노드값을 표시를 해준 후에 누적합을 이용하여 dp로 해주려 했는데,

실력부족 탓인지 만만치가 않아 어차피 시간내로 도는 스위핑으로 해주었다.

---

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <cstring>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, pi> pii;
typedef pair<ll, ll> pl;
const int MAX = 262150;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e16;
const int MOD = 1e9 + 7;
int N, a[MAX], k, x[MAX], y[MAX];
ll d[20][MAX];
vector<int> v[MAX];
vector<pii> p;
void dfs(int cur, int prev, int h) {
    y[cur] = h;
    for (int i : v[cur]) {
        if (i == prev)continue;
        dfs(i, cur, h + 1);
        if (!x[cur])
            x[cur] = ++k;
    }
    if (!x[cur])
        x[cur] = ++k;
}
bool cmp(pii p1, pii p2) {
    return p1.second.first < p2.second.first;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> N;
    ll ans = -LNF;
    for (int i = 1; i <= N; i++) {
        cin >> a[i];
        ans = max(ans, 1LL * a[i]);
        if (i > 1) {
            v[i / 2].push_back(i);
            v[i].push_back(i / 2);
        }
    }
    if (ans < 0) {
        cout << ans;
        return 0;
    }
    dfs(1, -1, 1);
    for (int i = 1; i <= N; i++) {
        p.push_back({ 1LL * a[i], { x[i],y[i] } });
    }
    sort(all(p), cmp);
    for (int i = 1; i <= 19; i++) {
        for (int j = i; j <= 19; j++) {
            ll M = 0;
            for (pii point : p) {
                int x = point.second.first;
                int y = point.second.second;
                ll n = point.first;
                if (y<i || y>j)continue;
                M = max(0LL, M + n);
                ans = max(ans, M);
            }
        }
    }
    cout << ans;
}

---

ㅠㅠ

아무튼 좋은 아이디어도 얻어냈고 재밌기도 했고 꽤 만족스러운 문제였다.