[백준 10167번] 금광

---

10167번: 금광

---

 

목차

• 사전 지식
• 문제 접근
• 문제 풀이

 

 

사전 지식

• 2차원 좌표 압축에 대한 개념을 알고 있어야 한다.
• 세그먼트 트리(Segment Tree)에 대한 기본 지식을 알고 있어야 한다. (링크)
• 가장 큰 연속합을 구하는 세그트리 문제를 이해하고 있어야 한다. (링크)

 

 

 

문제 접근

• 이 문제에 대한 순차적인 접근은 여기를 참고하기 바란다.

 

 

 

문제 풀이

이 문제의 핵심은 답이 되는 경우를 얼마나 효율적으로 탐색하는가이다.

(좌표 압축을 했다는 가정 하에) 가장 기초적인 방법은 후보가 되는 직사각형을 모두 살펴보는 것이고

이는 왼쪽 세로, 오른쪽 세로, 위 가로, 아래 가로를 선택하면 되므로 약 $N^4$가지의 경우가 나온다.

 

정답 풀이는 위 가로, 아래 가로 쌍만 살펴보며 답을 구하는 것이다.

이렇게 하면 $N^2$가지의 경우만 살펴보면 되기 때문에 답을 구할 수 있다.

우리가 해야 할 일은 위 가로와 아래 가로를 선택했을 때의 최적의 왼쪽 세로, 오른쪽 세로를 어떻게 구하냐는 것이다.

 

위 가로와 아래 가로를 확정 지었을 때 최적의 왼쪽 세로, 오른쪽 세로를 구한다는 말은

일차원에서 가장 큰 연속합을 구하는 문제로 바꿀 수 있다. (이 부분이 이해가 안 된다면 여기를 참고 바람)

(이를 구하는 법은 DP와 세그먼트 트리 풀이가 있으며, 이 문제 특성상 세그먼트 트리가 더 효율적이다)

 

정리하면, 위 가로와 아래 가로의 모든 쌍을 살펴보며 세그 먼트 트리를 이용하여 최적의 사각형(값)을 빠르게 찾아내는 것이다.

 

	// BOJ 10167
	// Struct SegTree
	#include <bits/stdc++.h>
	using namespace std;
	using ll = long long;
	ll INF = 1e14;
	struct point {
	int y, x, val;
	};
	vector<point> points;
	vector<array<ll,2>> y, x;
	vector<vector<array<ll,2>>> info_y;
	struct node {
	ll lmax, rmax, max, sum;
	};
	ll sz;
	vector<node> tree;
	node merge(node &l, node &r) {
	node ret;
	ret.lmax = max(l.lmax, l.sum+r.lmax);
	ret.rmax = max(r.rmax, r.sum+l.rmax);
	ret.max = max({l.max, r.max, l.rmax+r.lmax});
	ret.sum = l.sum + r.sum;
	return ret;
	}
	void update(ll idx, ll x) {
	idx += sz;
	ll tmp = tree[idx].max + x;
	tree[idx] = {tmp, tmp, tmp, tmp};
	while (idx /= 2) tree[idx] = merge(tree[2*idx], tree[2*idx+1]);
	}
	int main()
	{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	ll N; cin >> N;
	points.resize(N);
	x.resize(N); y.resize(N);
	info_y.resize(N);
	for (ll i=0; i<N; i++) {
	ll tx, ty, tval; cin >> tx >> ty >> tval;
	y[i] = {ty, i};
	x[i] = {tx, i};
	points[i].val = tval;
	}
	sort(y.begin(), y.end());
	sort(x.begin(), x.end());
	ll numy = 0, numx = 0;
	for (ll i=0; i<N; i++) { // Compress cordinate.
	if (i>0 && y[i-1][0]<y[i][0]) numy++;
	if (i>0 && x[i-1][0]<x[i][0]) numx++;
	points[y[i][1]].y = numy;
	points[x[i][1]].x = numx;
	}
	// Create info Array expressing 2-dimension Array.
	for (ll i=0; i<N; i++) {
	info_y[points[i].y].push_back({points[i].x, points[i].val});
	}
	sz = (1 << (ll)ceil(log2(N)));
	tree.assign(2*sz, {-INF, -INF, -INF, 0});
	int cnt = 0;
	for (ll j=sz; j!=0; j/=2) { // Initialize SegTree.
	for (ll i=j; i<min(2*j, sz+N); i++) {
	if (j == sz) tree[i] = {0, 0, 0, 0};
	else tree[i] = merge(tree[2*i], tree[2*i+1]);
	}
	}
	ll ans = 0;
	for (ll sy=0; sy<N; sy++)
	{
	if (sy%2 == 0)
	{
	for (ll ey=sy; ey<N; ey++) {
	for (auto &[tx, tval] : info_y[ey]) update(tx, tval);
	ans = max(ans, tree[1].max);
	}
	for (auto &[tx, tval] : info_y[sy]) update(tx, -tval);
	}
	if (sy%2 == 1)
	{
	for (ll ey=N-1; ey>=sy; ey--) {
	ans = max(ans, tree[1].max);
	for (auto &[tx, tval] : info_y[ey]) update(tx, -tval);
	}
	}
	}
	cout << ans << '\n';
	return 0;
	}

view raw 10167.cpp hosted with ❤ by GitHub