금광( BOJ 10167 )

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

10167번: 금광

 

문제 파악하기

x축과 y축에 평행한 직사각형 모양의 땅(R)에서 얻을 수 있는 최대 개발 이익을 구하는 문제입니다. R의 크기는 원하는 만큼 조정할 수 있으며, R의 범위 안에 있는 금광의 이익/손해를 모두 더한 값인 개발 이익이 될 수 있는 최댓값을 구해야 합니다. 금광의 위치가 1차원으로 이루어진 경우에는 1차원 배열을 이용한 연속된 구간의 최대합을 구하는 알고리즘을 사용할 수 있습니다. 하지만 현재 금광의 위치가 2차원으로 제시되었기 때문에 해당 알고리즘으로는 해결할 수 없습니다. 그렇다면 문제를 해결하기 위해서는 어떤 방법이 필요할까요?

 

문제 해결하기

해답은 단순합니다. 2차원이라 연속된 구간의 최대합을 구하지 못 했다면 금광의 위치를 1차원으로 변환하면 됩니다. 다만, 무작정 변환하는 것이 아니라 스위핑 기법을 사용하여 y값을 기준으로 1차원 배열에 저장할 수 있습니다. 예를 들어 입력 예시로 제시된 7개의 금광은 다음과 같이 1차원 배열로 저장될 수 있습니다.

  

y[1]	y[2]	y[3]	y[4]	y[5]	y[6]	y[7]	y[8]
-	5	(-1) + (-1)	-	3	-	(-1) + (-2)	2

 

우선, y의 최댓값만큼 배열을 만듭니다. 위의 예시에서는 최댓값이 8이므로 크기가 9인 배열 y를 만듭니다. 그리고 배열 y에는 인덱스에 해당하는 금광 y값이 나올 때마다 누적해서 값을 저장합니다. 위와 같이 금광의 맨 왼쪽 x값을 시작으로 한다면, 나머지 금광의 위치는 y값을 기준으로 누적해서 1차원 배열로 만들 수 있습니다. 누적할 때에는 각각의 금광의 x값을 기준으로 추가되며, x값이 같은 금광들은 한번에 추가해주면 됩니다. 이렇게 배열을 만들면서 각각의 x값이 추가될 때마다 연속된 누적합의 최댓값을 구하면 우리는 맨 왼쪽 x값을 기준으로 얻을 수 있는 최댓값을 알 수 있습니다. 

 

맨 왼쪽 금광의 x값을 기준으로 모든 금광의 위치를 1차원 배열에 누적했다면 이번에는 왼쪽에서 두 번째 금광의 x값을 기준으로 탐색을 하면 됩니다. 그리고 가장 오른쪽 금광의 x값이 나올 때까지 반복하면 우리가 원하는 결괏값을 얻을 수 있습니다. 다만, 이렇게 알고리즘을 설계하기에는 2가지 걸림돌이 있습니다.

 

첫 번째, y값의 범위가 너무 큽니다. y가 될 수 있는 최댓값은 10억이며, 10억개의 배열을 만들기에는 무리가 있습니다. 그렇기에 우리는 좌표 압축이라는 방법을 사용할 것입니다. 아무리 y의 최댓값이 크더라도 결국 3,000개의 입력에서 나올 수 있는 최대 경우의 수는 3,000개입니다. 따라서 우리는 모든 금광의 위치 좌표값을 정렬하고 중복된 값을 제거한 다음, 현재 인덱스의 값으로 위치값 (x, y)를 변환시켜 새롭게 저장할 것입니다. 예를 들어 위의 사례의 경우, { 2, 3, 5, 7, 8 }이라는 y값은 { 0, 1, 2, 3, 4 }라는 값으로 변환시키면 배열을 여유롭게 사용할 수 있습니다.

 

두 번째, 연속된 구간의 최대합을 구하는 알고리즘은 현저히 느립니다. 보통 1차원 배열에서 사용하는 알고리즘은 O(n)의 복잡도를 가지고 있습니다. 사실 O(n)이라는 시간복잡도는 매우 빠른 알고리즘이지만 문제는 이전에 2차원 금광 위치를 1차원으로 변환하는 알고리즘 자체에 O(n²)이라는 시간이 소요되었다는 점입니다. 만약 연속된 구간의 최대합을 구하는 알고리즘을 O(n)으로 설계한다면 전체 알고리즘의 시간복잡도는 O(n³)이 되며, 이러면 n의 범위에 의해 TL이 나오게 됩니다. 그럼 어떤 효율적인 알고리즘이 있을까요? 여기서 사용하는 방식이 바로 세그먼트 트리입니다.

 

흔히 금광세그라고 불리며 이 문제를 유명하게 만든 이 세그먼트 트리는 연속된 구간의 최대합을 O(logN)만에 구할 수 있게 만드는 자료구조입니다. 기존의 세그먼트 트리를 기반으로 만들어졌지만 조금 더 복잡한 세그먼트 트리입니다. 해당 세그먼트 트리에 대한 내용은 다음번에 포스팅 하겠습니다. 이렇게 알고리즘을 설계한다면 전체 시간 복잡도는 O(n2logN)이며, 이정도 시간 복잡도면 충분하다고 볼 수 있습니다.

 

소스코드

#include <stdio.h>
#include <vector>
#include <algorithm>
#define TMAX 1<<13
#define INF -3000000000L
using namespace std;
 
struct Pos {
    int x, y, w;
 
    bool operator< (const Pos &p) const { return x==p.x ? y<p.y:x<p.x; }
};
 
struct SegTree {
    long long int lmax, rmax, vmax, sum;
};
 
int N, x, y, w;
vector< Pos > inp;
vector< int > inpX, inpY;
 
int sz;
long long int ret;
SegTree segTree[TMAX];
 
int search(int k, vector< int > v) {
    int l, r, mid;
    l = 0; r = v.size()-1;
 
    while(l<=r) {
        mid = (l+r)/2;
 
        if(k == v[mid]) break;
        else if(k < v[mid]) r=mid-1;
        else l=mid+1;
    }
 
    return mid;
}
 
 
SegTree make_segTree(SegTree l, SegTree r) {
    SegTree ret;
 
    ret.lmax = max( l.lmax, l.sum+r.lmax );
    ret.rmax = max( r.rmax, r.sum+l.rmax );
    ret.sum = l.sum + r.sum;
 
    ret.vmax = max( max(l.vmax, r.vmax), max(ret.lmax, ret.rmax) );
    ret.vmax = max( ret.vmax, max(ret.sum, l.rmax+r.lmax) );
 
    return ret;
}
 
void update(int idx) {
    SegTree l, r;
 
    while(idx>0) {
        l = segTree[idx*2];
        r = segTree[idx*2+1];
 
        if(r.vmax == INF) segTree[idx] = l;
        else if(l.vmax == INF) segTree[idx] = r;
        else segTree[idx] = make_segTree(l, r);
 
        idx /=  2;
    }
}
 
SegTree search(int idx, int il, int ir, int sl, int sr) {
    SegTree l, r, ret;
    ret.vmax = INF;
 
    if(sl > sr) return search(idx, il, ir, sr, sl);
 
    if(ir < sl or sr < il) return ret;
    else if(sl<=il and ir<=sr) return segTree[idx];
    else {
        l = search(idx*2, il, (il+ir)/2, sl, sr);
        r = search(idx*2+1, (il+ir)/2+1, ir, sl, sr);
 
        if(r.vmax == INF) return l;
        else if(l.vmax == INF) return r;
        else return ret = make_segTree(l, r);
    }
}
 
int main() {
    // 입력
    scanf("%d", &N);
    for(int i=1;i<=N;i++) {
        scanf("%d %d %d", &x, &y, &w);
 
        inp.push_back({x, y, w});
        inpX.push_back(x); inpY.push_back(y);
    }
 
    // 정렬
    sort(inp.begin(), inp.end());
 
    // 좌표 압축
    sort(inpX.begin(), inpX.end());
    inpX.erase(unique(inpX.begin(), inpX.end()), inpX.end());
 
    sort(inpY.begin(), inpY.end());
    inpY.erase(unique(inpY.begin(), inpY.end()), inpY.end());
 
    // inp의 좌표값 변환
    for(int i=0;i<N;i++) {
        inp[i].x  = search(inp[i].x, inpX);
        inp[i].y = search(inp[i].y, inpY);
    }
 
 
    // 2개의 x축 사이의 모든 좌표값을 1차원 배열로 변환하여 최대 구간합 구하기
    ret = INF;
    for(sz=1;sz<inpY.size();sz*=2);
 
    // x1: 기준이 되는 x값
    for(int x1=0;x1<inpX.size();x1++) {
        // 세그먼트 트리 초기화
        for(int idx=1;idx<sz*2;idx++) segTree[idx] = {0, 0, INF, 0};
 
        // 세그먼트 트리에 값 넣기
        for(int idx=0;idx<N;idx++) {
            // 중복된 탐색 제거
            if(inp[idx].x < x1) continue;
 
            // 현재 금광을 1차원 세그먼트 트리에 넣기(y 위치) >> 중복된 위치는 누적
            long long int tmp = segTree[sz+inp[idx].y].sum + inp[idx].w;
            segTree[sz+inp[idx].y] = {tmp, tmp, tmp, tmp};
            update((sz+inp[idx].y)/2);
 
            // x값이 같은 금광은 한 번에 추가한 다음에 최댓값 탐색
            if(idx+1<N and inp[idx].x == inp[idx+1].x) continue;
            else ret = max( ret, segTree[1].vmax );
        }
    }
 
    // 출력
    printf("%lld", ret);
 
}
 
/*
4
2 2 4
1 2 6
2 1 7
1 1 -1000
ans: 11
*/

후기

정말 오랜 시간이 걸려 해결한 문제입니다. 특히 금광의 위치인 2차원 값을 1차원 배열로 변환한다는 생각을 떠올리는데 오랜 시간이 걸렸고, 연속된 구간의 최대합을 세그먼트 트리로 구현하는데에도 많은 시간이 걸린 문제입니다. 특히 마지막 반례(https://www.acmicpc.net/board/view/4498)를 해결하는데 어려움을 겪었던 게 기억에 많이 남습니다. 문제를 풀어본 총평은 아직은 스위핑 기법을 사용하는데 어려움을 느껴 이번 기회에 스위핑 기법을 연습해보려 합니다.