[BOJ] 10167 : 금광

문제 : https://www.acmicpc.net/problem/10167

---

세그먼트트리 분할정복 좌표압축

[ 문제해석 ]

 2차원 평면에 N개의 금광이 존재하고, 금광마다 벌 수 있는 수익이 다 다르다. x축과 y축에 평행한 직사각형을 그려서 직사각형 안에 있는 금광으로 얻을 수 있는 최대 수익을 구해보자.

 

[ 알고리즘풀이 ]

 N이 3000으로 우리는 O(N^2 * logN) 이나 O(N^2) 로 문제를 해결해야한다.

 문제를 단순화해보자.

 

1)  직사각형을 그릴 때 금광이 없는 x값, y값에다가 굳이 직사각형을 그릴 필요가 없다.

 위의 그림과 같이 금광 4개를 포함하는 직사각형은 여러가지 경우가 있지만 우리는 '직사각형2'처럼 금광들의 x값, y값을 기준으로 포함하는 가장 작은 직사각형만 그려봐도 된다!

--> 금광을 기준으로 직사각형을 그리자.

--> 금광 2개를 정하면 그 금광을 기준으로 직사각형을 그릴 수 있고, 금광 2개를 선택하는 경우는 O(N^2) 으로 가능하다!

 

2) 선분 S가 있고, 그 위에 값들이 있을 때 다음과 같은 식이 성립한다.

먼저, 4개의 용어를 정의하겠다.

 

 sum = 선분 위에 있는 모든 값들의 합

 lsum = 선분의 맨 왼쪽에 있는 값부터 시작해서 연속된 최대 합

 rsum = 선분의 맨 오른쪽에 있는 값부터 시작해서 연속된 최대 합

 maxsum = 선분에서 얻을 수 있는 연속된 최대합

 

 그 후, 선분 S를 선분 L(left)와 선분 R(right)로 나눈 상황에서 선분 S의 sum, lsum, rsum, maxsum 을 어떻게 구할 수 있을지 생각해보자.

 

[sum]

 선분 S의 모든 값들의 합 = 선분 L의 모든 값의 합 + 선분 R의 모든 값의 합 이 성립한다.

 즉, Ssum = Lsum + Rsum 이 성립하고 이는 설명이 필요 없으니 넘어가겠다.

 

[lsum]

 선분 S의 맨 왼쪽부터 시작해서 연속된 최대 합에 대해서 생각해보자.

 선분 S의 맨 왼쪽에서 시작해서 연속된 최대 합은 선분 L의 범위에서 끝날 수도 있고, 선분 L의 범위를 다 포함하며 선분 R의 범위에서 끝날 수도 있다. 

 선분 L의 범위에서 끝났다면 그건 Llsum 이랑 동일하고, 선분 R의 범위에서 끝났다면 선분 L의 범위 값들을 다 합한 값과 Rlsum 을 합한 값이 될 것이다.

 즉, Slsum = max( Llsum, Lsum + Rlsum ) 이 성립한다.

 

[rsum]

 lsum과 마찬가지로 선분 S의 맨 오른쪽부터 시작해서 연속된 최대 합은 다음과 같다.

 Srum = max( Rrsum, Lrsum + Rsum )

 

[maxsum]

 이제 우리가 최종적으로 원하는 maxsum에 대해서 생각해보자. 선분 S에서 연속된 최대 합은 4개로 나눌 수 있다. 첫 번째는 선분 S에 있는 모든 값들을 다 합하는게 최대 합일 수가 있다. 또, 선분 L 범위에서 연속된 최대 합이 나오거나, 선분 R 범위에서 연속된 최대 합이 나오거나 아니면 마지막으로 선분 L과 R를 걸쳐서 연속된 최대 합이 나올 수 있다. 선분 L과 R을 걸쳐서 연속된 최대 합이 나오는 경우는 선분 L의 오른쪽에서 시작한 최대 합과 선분 R의 왼쪽에서 시작한 최대합을 연결한 값이 된다.

 따라서, Smaxsum = max ( Ssum , Lmaxsum, Rmaxsum, Lrsum + Rlsum ) 이 성립한다.

 

3) 이제, 1) 과 2) 를 이용해 문제를 해결해보자.

 1)에 의해 우리는 금광 2개를 정하면 직사각형을 정할 수 있다.

 --> 우리는 금광들의 y값 중에 2개를 선택해 먼저, 직사각형의 y 범위를 지정할 것이다.

 

 예제를 통해서 생각해보자.

 위와 같은 예시에서 y의 범위를 [2, 3] 으로 2개 선택해 지정한다면 우리는 (3, 3) / (7, 3) / (10, 2) 금광 3개를 생각해볼 수 있다. 이 금광들을 그냥 x축으로 내려서 (3) / (7) / (10) 에 있다고 생각을 하고 3에 있는 금광은 cost가 -1, 7에 있는 금광은 cost가 -1, 10에 있는 금광은 cost가 5 이므로 문제를 단순화시켜서 x축 위에 있는 금광들의 연속된 최대 합에 대해서 생각해보면 된다.

 즉, y를 2개 선택해서 범위를 지정하고 해당 범위에 있는 금광들을 다 x축으로 내린 다음에 2) 의 정의를 이용해 x축 구간의 연속된 최대 합을 구할 수 있다. 그러면 이는 직사각형을 그려서 최대 이익을 구하는 것과 동일하다.

 마지막으로, 구간의 연속된 최대 합이므로 자료구조 세그먼트 트리에 2) 공식을 적용해서 구하면 된다.

[ 코드 C++ ]

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define ll long long
 
using namespace std;
 
struct Point {
    int x, y, w;
};
 
struct Tree {
    ll lsum, rsum, sum, maxsum;
};
 
int N, leaf_size;
ll res = 0;
vector<int> x, y;
vector<Point> p;
Tree t[8192];
 
bool cmp(Point a, Point b) {
    if (a.y == b.y) return a.x < b.x;
    return a.y < b.y;
}
 
void clear(void) {
    for (int i = 0; i < 8192; i++)
        t[i].lsum = t[i].rsum = t[i].sum = t[i].maxsum = 0;
}
 
void update(int n, int w) {
    int c = leaf_size + n;
    t[c].lsum = t[c].rsum = t[c].sum = t[c].maxsum += w;
    while (c > 1) {
        c /= 2;
        int l = 2 * c, r = 2 * c + 1;
        t[c].sum = t[l].sum + t[r].sum;
        t[c].lsum = max(t[l].lsum, t[l].sum + t[r].lsum);
        t[c].rsum = max(t[r].rsum, t[l].rsum + t[r].sum);
        t[c].maxsum = max(max(t[l].rsum + t[r].lsum, t[c].sum), max(t[l].maxsum, t[r].maxsum));
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> N;
    leaf_size = 1 << ((int)ceil(log2(N)));
 
    for (int i = 0, j, k, l; i < N; i++) {
        cin >> j >> k >> l;
        p.push_back({ j, k, l });
        x.push_back(j);
        y.push_back(k);
    }
    // 좌표압축과정
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    x.erase(unique(x.begin(), x.end()), x.end());
    y.erase(unique(y.begin(), y.end()), y.end());
 
    for (int i = 0; i < p.size(); i++) {
        p[i].x = lower_bound(x.begin(), x.end(), p[i].x) - x.begin();
        p[i].y = lower_bound(y.begin(), y.end(), p[i].y) - y.begin();
    }
    sort(p.begin(), p.end(), cmp);
 
    // 이제 y값 후보 중에서 2개를 뽑는 모든 경우에서 최대로 얻을 수 있는 이득을 계산하자!
    for (int i = 0; i < y.size(); i++) {
        clear();
        int k = 0;
        while (k < p.size() && p[k].y < i)
            k++;
        for (int j = i; j < y.size(); j++) {
            while (k < p.size() && i <= p[k].y && p[k].y <= j) {
                update(p[k].x, p[k].w);
                k++;
            }
            res = max(res, t[1].maxsum);
        }
    }
    cout << res << '\n';
    return 0;
}

https://github.com/travelbeeee/BOJ/blob/master/BOJ10167.cpp

---