[BOJ] 10167번: 금광

 

10167번: 금광

사용 알고리즘

• plane sweeping
• segment tree

시간 복잡도

• O($N^2 log N$)

---

풀이

N이 최대 3000이기 때문에 시간 복잡도가 최대 O($N^2 logN$)인 알고리즘을 사용하여야 한다.

 

금광들을 직사각형 모양의 영역으로 묶어 이익을 확인할 경우,

금광들의 가장 좌측 상단에 있는 금광과 가장 우측 하단에 있는 금광을 기준으로 직사각형을 만들 수 있다.

따라서 금광들의 위치만으로 분할정복을 통해 구간의 합을 구하는 문제로 접근할 수 있다. 

x축을 sweeping한 후 y축을 기준으로 세그먼트 트리를 구현할 때 각 구간에서는 합은 다음과 같이 정의한다.

 

• lsum  -> 구간의 왼쪽 끝에서부터의 연속한 원소의 최대 합
• rsum  -> 구간의 오른쪽 끝에서부터의 연속한 원소의 최대 합
• tsum  -> 구간의 모든 원소의 합
• msum -> 구간에서 나올 수 있는 최대 연속합

구간의 합은 세그먼트 트리를 이용하여 업데이트와 쿼리를 O($logN$)에 구할 수 있다.

따라서 구간의 왼쪽 끝의 x축을 기준으로 잡고 오른쪽 끝의 x축을 늘려가며 업데이트와 쿼리를 통해 확인해 주면 된다.

이때, x축을 늘려가며 업데이트를 진행할 때 같은 x 좌표의 y축 값들은 동시에 업데이트를 진행해주어야 한다.

 

x축을 늘릴 때마다 각 점당 O($logN$)씩 걸리게 되고

왼쪽 끝의 x축을 기준으로 오른쪽의 모든 점들을 업데이트와 쿼리를 진행했을 때 O($NlogN$)이 걸린다.

따라서 모든 x축에 대해서 왼쪽 끝의 x축을 변경할 때 세그먼트 트리를 초기화 후 진행하면 O($N^2 log N$)이 걸린다.

 

x축 기준으로 좌표 압축하여 동일 x축 상의 y 좌표를 한 번에 업데이트할 수 있도록 진행하고,

y축 기준으로 좌표 압축하여 세그먼트 트리의 리프 노드를 최대 N만큼만 사용할 수 있게 만들어 준다.

 

x축 압축은 편의상 진행을 해준 경우지만,

y축 압축은 하지 않으면 리프 노드 수를 좌표 범위($10^9$) 만큼 잡아야 하기에 좌표 압축을 반드시 해주어야 한다.

---

소스코드

#include <bits/stdc++.h>
using namespace std;

class Node {
public:
	long long tsum, lsum, rsum, msum;
	
	Node() : tsum{ 0 }, lsum{ 0 }, rsum{ 0 }, msum{ 0 } {};
	Node sum(int val) {
		this->tsum += val;
		this->lsum = this->rsum = this->msum = this->tsum;
		return *this;
	}
	Node merge(const Node& left, const Node& right) {
		this->tsum = left.tsum + right.tsum;
		this->lsum = max(left.lsum, left.tsum + right.lsum);
		this->rsum = max(right.rsum, left.rsum + right.tsum);
		this->msum = max({ left.rsum + right.lsum, left.msum, right.msum, this->lsum, this->rsum });
		return *this;
	}
};

class Dot {
public:
	int x, y, w;

	Dot() {};
	Dot(int x, int y, int w) : x{ x }, y{ y }, w{ w } {};
};

long long res;
int N, xs_len, ys_len;

vector < Node > tree;
vector < int > xs, ys;
vector < Dot > dot_list;
vector < vector<Dot> > zip;

Node update(int inx, int val, int node, int x, int y) {
	if (y < inx || inx < x)
		return tree[node];
	if (x == y)
		return tree[node].sum(val);

	int mid = (x + y) >> 1;
	return tree[node].merge(update(inx, val, node * 2, x, mid), update(inx, val, node * 2 + 1, mid + 1, y));
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	cin >> N;
	dot_list.resize(N);
	for (Dot& dot : dot_list) {
		cin >> dot.x >> dot.y >> dot.w;
		xs.push_back(dot.x);
		ys.push_back(dot.y);
	}
	sort(xs.begin(), xs.end());
	sort(ys.begin(), ys.end());

	xs.erase(unique(xs.begin(), xs.end()), xs.end());
	xs_len = xs.size();
	ys.erase(unique(ys.begin(), ys.end()), ys.end());
	ys_len = ys.size();

	zip.resize(xs_len);
	for (Dot& dot : dot_list) {
		int x = lower_bound(xs.begin(), xs.end(), dot.x) - xs.begin();
		int y = lower_bound(ys.begin(), ys.end(), dot.y) - ys.begin();

		zip[x].push_back(Dot(x, y, dot.w));
	}

	for (int i = 0; i < xs_len; i++) {
		tree.resize(ys_len * 4);

		for (int j = i; j < xs_len; j++) {
			for (Dot& k : zip[j])
				update(k.y, k.w, 1, 0, ys_len - 1);
			res = max(tree[1].msum, res);
		}

		tree.clear();
	}

	cout << res;

	return 0;
}

 

Support by 강태종