[BOJ] 10167. 금광

 

10167번: 금광

어떤 2차원 그래프에서, 가능한 직사각형 모양의 범위 내부에 있는 정점의 값의 합 중 최댓값을 구하는 문제입니다.

좌표 x, y의 범위는 (0 ≤ x,y ≤ 10^9)인데, 정점의 개수는 최대 3000개이므로 좌표 압축을 사용해 (0 ≤ x,y < 3000) 으로 만들어줍니다.

시간 제한은 3초이므로 O(N^2logN) 으로 해결하면 됩니다.

일반적으로 사각형을 선택하는 기준은 세로 선 두 개, 가로 선 두 개로 O(N^4)라고 생각할 수 있는데 이러면 시간이 너무 많이 걸리므로 다른 방법을 생각해야 합니다.

우선 y축을 for문으로 돌며, 두 개의 가로선을 선택하는 것을 기준으로 하도록 했습니다. 여기서 N^2입니다.

또 세그먼트 트리를 이용하면 구간 합을 빠르게 구할 수 있으므로 세그먼트 트리를 사용하려고 생각했습니다.

기본적인 아이디어는, for문으로 방문하는 각 y값에 해당하는 가중치들을 더하거나 / 빼면서 세그먼트 트리를 이용해서 최댓값을 구하는 것이었습니다.

그런데 일반적인 세그먼트 트리에서는 구간 합을 저장할 수는 있지만 각 구간 합의 최댓값을 구하기는 어렵습니다.

그래서 이 문제에서 세그먼트 트리에는 단순히 구간 합만 저장하는 것이 아니라, 자식 노드의 정보로 부모 노드에서 해당 구간의 구간 합의 최댓값을 알 수 있도록 4개의 값을 저장합니다.

 

struct segnode
{
    long long l;
    long long r;
    long long val;
    long long all;
};
int treeIndex[3000];
segnode segTree[8192];

 

L은 해당 노드 범위의 왼쪽에서 시작하는 구간 합의 최댓값,

R은 해당 노드 범위의 오른쪽에서 시작하는 구간 합의 최댓값,

VAL은 해당 노드 범위의 모든 구간 합 중 최댓값,

ALL은 해당 노드 범위의 전체 합을 저장합니다.

 

이렇게 하면,

자식 노드 범위의 최대 구간 합과 (그림에서는 각각 7, 15)

왼쪽 자식 노드의 오른쪽부터 시작하는 최대 구간 합 (R) + 오른쪽 자식 노드의 왼쪽부터 시작하는 최대 구간 합(L) (그림에서는 7) 을 비교하여 그 중 최댓값을 부모 노드의 VAL값으로 정할 수 있습니다.

 

마찬가지로 부모 노드의 L값은 왼쪽 자식 노드의 L값과 왼쪽 자식 노드의 ALL값 + 오른쪽 자식 노드의 L값 중 최댓값으로 정할 수 있습니다.

 

이를 코드로 표현하면

 

void init(int index, int S, int E)
{
    if (S == E)
    {
        treeIndex[S] = index;
        return;
    }
    init(index * 2 + 1, S, (S + E) / 2);
    init(index * 2 + 2, (S + E) / 2 + 1, E);
}

void update(int index, long long val)
{
    int i = treeIndex[index];
    segTree[i].l += val;
    segTree[i].r += val;
    segTree[i].val += val;
    segTree[i].all += val;
    if (i == 0)
        return;
    i = (i - 1) / 2;
    while (i >= 0)
    {
        segTree[i].l = max(segTree[i * 2 + 1].l, segTree[i * 2 + 1].all + segTree[i * 2 + 2].l);
        segTree[i].r = max(segTree[i * 2 + 2].r, segTree[i * 2 + 2].all + segTree[i * 2 + 1].r);
        segTree[i].val = max(segTree[i * 2 + 1].r + segTree[i * 2 + 2].l, max(segTree[i * 2 + 1].val, segTree[i * 2 + 2].val));
        segTree[i].all = segTree[i * 2 + 1].all + segTree[i * 2 + 2].all;
        if (i == 0)
            break;
        else
            i = (i - 1) / 2;
    }
}

 

위와 같습니다.

 

금광 문제에서는 이렇게 세그트리를 만들어두고, y값의 범위를 조절해가며 해당 y값의 정점들을 세그먼트 트리에 넣고 빼면서 각 경우의 세그트리 루트의 VAL값 중 최댓값을 저장해두면 됩니다.

 

bool isForward = true;
long long ans = 0;
for (int i = 0; i < y_size; i++)
{
    if (isForward)
        for (int j = i; j < y_size; j++)
        {
            for (node n : vec[j])
            {
                update(n.x, n.w);
            }
            ans = max(ans, segTree[0].val);
        }
    else
    {
        for (node n : vec[i - 1])
        {
            update(n.x, -n.w);
        }
        ans = max(ans, segTree[0].val);
        for (int j = y_size - 1; j >= i; j--)
        {
            for (node n : vec[j])
            {
                update(n.x, -n.w);
            }
            ans = max(ans, segTree[0].val);
        }
    }
    isForward = !isForward;
}

 

저는 이런 식으로 구현했습니다. 시작 y값(i)은 1씩 증가하고, 끝 y값(j)은 내려갔다가 올라갔다가 하는 방식입니다. 내려갈 때는 y=j인 정점들을 더해주고 올라갈 때는 빼주면서 최댓값을 구합니다.

 

9분만에 예외케이스 발견하고 수긍

99퍼에서 틀릴 수도 있습니다. (저는 정점이 한 개일 때의 예외처리 안 해서 틀렸습니다. 예외처리를 꼭 합시다.)