[백준 2574] 마법색종이

예전이 \(N^2\)로 작성해서 AC를 받았었는 데 저격 tc가 들어와서 다시 풀어보았다. 이 문제가 초등부 문제이지만, 다이아몬드 \(4\)로 책정이 되어있는 데 원래 정올에서 의도한 풀이는 이진 트리를 이용한 풀이가 정해인가 보다. 데이터가 약해서 정올 사이트에서 AC를 받는다.

1.풀이

먼저 첫번째로 접근한 방법은 각 한개의 점마다 각각의 사각형으로 나누고, 다음 점이 어느 사각형에 포함되는 지를 빠르게 찾아서 계속 분할해나가는 풀이를 생각했다. 하지만 점이 분할한 사각형 중에 어디에 속하는 지 빠르게 찾을 방법이 떠오르지 않았다. 여기서 다르게 생각해서 문제를 풀어보자.

각 한개씩 점을 가지고 분할하는 것이 아닌 현재 분할된 사각형에 포함되는 점들을 모두 넣어두고 분할한다는 생각을 해보자. 첫번째 가장 큰 사각형에는 모든 점을 가지고 있을 것이며, 다음 분할되는 순서는 그 사각형 안에 포함되는 점들 중 가장 빠른 순서의 점으로 다음 사각형으로 분할 할 것이다.

이때 분할된 사각형으로 현재 사각형에 포함된 점들을 옮기는 작업을 할 것이다. 한개의 집합에서 두개의 집합으로 분리하는 데 최악의 경우에는 \(O(N)\)이므로 Small To Large 테크닉 처럼 더 작은 집합들이 만들어지는 곳에만 새롭게 집합을 만들어주자. 그러면 시간복잡도는 \(O(logN)\)을 가지게 된다.

이때 분할된 사각형에서 점들을 관리하는 방법은 set이나 다른 자료구조를 사용해서 관리해주므로 시간복잡도는 \(O(Nlog^2N)\)이 나온다.

2. 소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;


#define x first
#define y second


struct Q {
    int x, y, idx, num;
    Q(int _x, int _y, int _idx, int _num) {
        x = _x, y = _y, idx = _idx; num = _num;
    }
};
struct cmp1 {
    bool operator()(const Q& a, const Q& b) const {
        return a.x < b.x;
    }
};
struct cmp2 {
    bool operator()(const Q& a, const Q& b) const {
        return a.y < b.y;
    }
};
pi query[30001];


int rmin = INT_MAX, rmax = 0;


void dnc(int x1, int y1, int x2, int y2, bool black, 
    set<int>& idx, set<Q, cmp1>& sx, set<Q, cmp2>& sy) {
    if (idx.size() == 0) {
        int v = (x2 - x1) * (y2 - y1);
        rmin = min(rmin, v);
        rmax = max(rmax, v);
        return;
    }


    pi now = query[*idx.begin()];
    idx.erase(idx.begin());
    sx.erase(Q(now.x, now.y, 0, 0));
    sy.erase(Q(now.x, now.y, 0, 0));


    set<int> tidx;
    set<Q, cmp1> tsx;
    set<Q, cmp2> tsy;


    int num = 0;


    if (!black) {
        auto pos = sy.lower_bound(Q(0, now.y, 0, 0));
        int cnt = sy.size();
        if (pos != sy.end()) cnt = pos->num;


        if (cnt < (sy.size() - cnt)) {
            for (auto itr = sy.begin(); itr != pos;) {
                Q top = *itr;
                sx.erase(top); itr = sy.erase(itr);
                idx.erase(top.idx);
                top.num = num++;
                tsy.insert(top);
                tsx.insert(top);
                tidx.insert(top.idx);
            }


            dnc(x1, y1, x2, now.y, !black, tidx, tsx, tsy);
            dnc(x1, now.y, x2, y2, !black, idx, sx, sy);
        }
        else {
            for (auto itr = pos; itr != sy.end();) {
                Q top = *itr;
                sx.erase(top); itr = sy.erase(itr); 
                idx.erase(top.idx);
                top.num = num++;
                tsy.insert(top);
                tsx.insert(top);
                tidx.insert(top.idx);
            }


            dnc(x1, y1, x2, now.y, !black, idx, sx, sy);
            dnc(x1, now.y, x2, y2, !black, tidx, tsx, tsy);
        }
    }
    else {
        auto pos = sx.lower_bound(Q(now.x, 0, 0, 0));
        int cnt = sx.size();
        if (pos != sx.end()) cnt = pos->num;


        if (cnt < (sx.size() - cnt)) {
            for (auto itr = sx.begin(); itr != pos;) {
                Q top = *itr;
                sy.erase(top); itr = sx.erase(itr);
                idx.erase(top.idx);
                top.num = num++;
                tsy.insert(top);
                tsx.insert(top);
                tidx.insert(top.idx);
            }


            dnc(x1, y1, now.x, y2, !black, tidx, tsx, tsy);
            dnc(now.x, y1, x2, y2, !black, idx, sx, sy);
        }
        else {
            for (auto itr = pos; itr != sx.end();) {
                Q top = *itr;
                sy.erase(top); itr = sx.erase(itr);
                idx.erase(top.idx);
                top.num = num++;
                tsy.insert(top);
                tsx.insert(top);
                tidx.insert(top.idx);
            }


            dnc(x1, y1, now.x, y2, !black, idx, sx, sy);
            dnc(now.x, y1, x2, y2, !black, tidx, tsx, tsy);
        }
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);


    int n, m; cin >> n >> m;
    int k; cin >> k;
    set<int> idx;
    set<Q, cmp1> sx;
    set<Q, cmp2> sy;
    for (int i = 0; i < k; i++) {
        int x, y; cin >> x >> y;
        query[i].x = x; query[i].y = y;
        idx.insert(i);
        sx.insert(Q(x, y, i, i));
        sy.insert(Q(x, y, i, i));
    }


    dnc(0, 0, n, m, false, idx, sx, sy);


    cout << rmax << " " << rmin;


    return 0;
}