[BOJ 10167] 금광

[BOJ 10167]금광 - D5

문제 설명

2차원 좌표평면상에서 [x좌표,y좌표,가중치]가 한 세트로 이루어진 정보가 N개 주어진다. 우리는 이 좌표평면 상에서 적당한 직사각형을 만들어서 그 직사각형 내부에 있는 가중치가 최대가 되도록 만들면 된다.

문제 풀이

2차원 좌표평면이 나오므로 일단 하나의 축을 기준으로 정렬하고 라인스위핑으로 푸는 방법을 생각했다. y좌표를 오름차순으로 먼저 정렬해놓고, x좌표를 컨트롤 하면 될 것 같다. (반대로 해도 상관없다)

이 문제의 경우에는 먼저 직사각형의 바닥과 천장(y좌표)를 픽스해둔 상태에서, 그 범위 안에 들어오는 x좌표를 왼쪽 -> 오른쪽 방향으로 쭉 저장해놓는다. 이렇게 하고 나면 이 문제를 '가장 큰 연속하는 부분수열의 합' 문제로 바꿀 수 있게 된다. 그렇다면 '가장 큰 연속하는 부분수열의 합'은 어떻게 구할까?

여기선 4개의 배열이 필요하다. 2진트리의 형태로 구성한다고 할 때

원소의 총합(sum), 왼쪽 자식의 최대값(lMax), 오른쪽 자식의 최대값(rMax), 전체의 최대값(totalMax)

가 필요하다.
그래서 각 segment가 합쳐질 때 필요한 연산이 아래 첨부한 소스코드 update()함수의 while문 안에 들어있다.
이 연산 과정을 통해 최종적으로 '가장 큰 연속하는 부분수열의 합'은 totalMax[1] 값에 들어있게 된다. 이 과정을 직사각형의 바닥과 천장을 2중 for문을 활용하여 모든 케이스에 대해 조사하여 그 중에서 가장 큰 가중치의 합을 찾으면 된다.

비슷한 문제

[BOJ 16993]연속합과 쿼리 - P2

금광 문제에서 '가장 큰 연속하는 부분수열의 합' 부분만 똑 떼어내면 아래 문제처럼 된다.

소스 코드

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int SIZE = 3009;
ll totalMax[SIZE*8],lMax[SIZE*8],rMax[SIZE*8],sum[SIZE*8];
map<int,int> xComp,yComp;
map<int,vector<pii>> yCord;
vector<int> yVec;
int n,startIdx=1;

void update(int node,int k){
    node = node + startIdx - 1;
    lMax[node] += k;
    rMax[node] += k;
    sum[node] += k;
    totalMax[node] += k;
    node /= 2;

    while(node >= 1){
        int lCh = node*2,rCh = node*2+1;
        sum[node] = sum[lCh] + sum[rCh];
        lMax[node] = max(lMax[lCh], sum[lCh] + lMax[rCh]);
        rMax[node] = max(rMax[rCh], sum[rCh] + rMax[lCh]);
        totalMax[node] = max({totalMax[lCh], totalMax[rCh], rMax[lCh] + lMax[rCh]});
        node /= 2;
    }
}

void clear(){
    for(int i=0 ; i<=startIdx * 2 ; i++){
        sum[i] = lMax[i] = rMax[i] = totalMax[i] = 0;
    }
}

int main(){
    scanf("%d",&n);

    for(int i=1 ; i<=n ; i++){
        int a,b,w;    scanf("%d %d %d",&a,&b,&w);
        xComp[a] = yComp[b] = 1;
        yCord[b].push_back({w,a});
    }

    int xCnt = 1;
    for(auto &here : xComp){
        here.second = xCnt++;
    }
    int yCnt = 1;
    for(auto &here : yComp){
        here.second = yCnt++;
        yVec.push_back(here.first);
    }

    for(;startIdx < xCnt - 1 ; startIdx *= 2);

    ll ans = 0;

    for(int i=0 ; i<yCnt-1 ; i++){
        clear();
        for(int j=i ; j<yCnt-1 ; j++){
            for(auto &here : yCord[yVec[j]]){
                int w = here.first,x = here.second, idx = xComp[x];
                update(idx,w);
            }
            ll cur = totalMax[1];
            ans = max(ans, cur);
        }
    }
    printf("%lld\n",ans);

    return 0;
}