[BOJ] 백준 10167. 금광 (Diamond V)

엄청나게 높은 난이도임에도 불구하고, KOI 고등부도 아닌 중등부에 나와서 굉장히 유명해진 문제.

이 문제의 하위호환이 https://www.acmicpc.net/problem/16993 인데, 이것마저도 나에겐 굉장히 어려웠다.

위 문제를 푼 이유가 바로 '금광'을 해결하기 위해서일 정도로 이 문제는 웰노운인데,

이번 기회에 복습 겸 포스팅해보려 한다.

 

문제는 아래와 같다.

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

10167번: 금광

---

의식의 흐름 및 해설

 - 누적합과 좌표압축으로 가능하지 않을까?

우선 좌표의 범위가 말도 안되게 크기 때문에 좌표압축을 해주어야한다.

문제가 딱봐도 누적합처럼 생겼고, 누적합이나 세그먼트트리에선 개인적으로 1-index가 편하기 때문에 1-index로 처리해주었다.

    // x, y값이 서로 독립적이기 때문에 따로 좌표압축을 해준다.
	for (int i = 1; i <= N; i++) {
		cin >> p[i].x >> p[i].y >> p[i].cost;
		tmpX[i] = { p[i].x, i };
		tmpY[i] = { p[i].y, i };
	}
	sort(tmpX + 1, tmpX + N + 1);
	sort(tmpY + 1, tmpY + N + 1);
    // x값에 대해 좌표압축
    // 서로 같은 x값일 경우 같은 x값을 가지도록
	for (int i = 1; i <= N; i++) {
		if (i != 1 && tmpX[i - 1].first != tmpX[i].first)
			Mx++;
		p[tmpX[i].second].x = Mx;
	}
    // y값에 대해 좌표압축
    // 서로 같은 y값일 경우 같은 x값을 가지도록
	for (int i = 1; i <= N; i++) {
		if (i != 1 && tmpY[i - 1].first != tmpY[i].first)
			My++;
		p[tmpY[i].second].y = My;
	}

그럼 이제 좌표압축도 됐고,

누적합 개념도 알고 있으니 O(N^2)에 해볼까~?

이거이거~ update하는 부분도 없으니 아래 문제처럼 세그먼트트리 없이 이차원 누적합으로 O(N^2)에 할 수 있겠는걸~? https://www.acmicpc.net/problem/15724

15724번: 주지수

 

라고 생각할 수 있다.

그러나 세그먼트트리 없이는 O(N^2)이 절대 불가능함을 조금만 생각해보면 알 수 있다. (세그먼트트리로 해도 O(N^2)은 불가능하다...)

 

참고로 위 문제도 특정영역의 직사각형 부분 넓이를 구하라는 것이지, 특정영역의 최댓값을 구해주기 위해서는 O(N^2)만에 절대 불가능하다. 최댓값을 구하기 위해선 결국 모든 영역의 쿼리를 다 해봐야되는데, 세그먼트트리의 update가 있지 않는 이상 TLE이기 때문이다.

 

위 방법처럼 할 경우, 시간복잡도는 대략 아래와 같다.

직사각형 영역의 왼쪽 x축을 Sx, 오른쪽 x축을 Ex, 아래 y축을 Sy, 위 y축을 Ey라 하자.

Sy가 고정됐다고 가정해보자. 좌표압축을 했으니 1<=x<=3000, 1<=y<=3000일텐데, Ey가 자유자재로 움직이고, 그 안에서 Sx, Sy도 따로따로 움직이므로 O(3000C2 * 3000C2)의 시간복잡도가 나오게 되는 것이다! Wow....

---

 - 그럼 어떻게 해야 할까?

위 과정을 통해 update가 필요한 이유를 알았다.

따라서 우리는 연속합 세그먼트트리를 이용해야 한다.

연속합 세그먼트트리 코드는 아래 깃허브 주소를 참고하자.

https://github.com/kth990303/Baekjoon/blob/master/Standard/16993_segtree.cpp

GitHub - kth990303/Baekjoon: 백준 문제들을 풀고 올리는 레포지토리

대략 설명을 하자면 아래와 같다.

struct Node {
	ll lsum, rsum, sum, maxsum;
};
Node merge(Node A, Node B) {
	return {
    	// s~mid 일부분 vs s~mid + mid+1~일부분
		max(A.lsum, A.sum + B.lsum),
        // mid+1~e 일부분 vs 일부분~e
		max(B.rsum, B.sum + A.rsum),
		A.sum + B.sum,
        // A(s~mid) 최대 vs B(mid+1~e) 최대 vs A일부+B일부
		max({ A.maxsum,B.maxsum,A.rsum + B.lsum })
	};
}

prefix_sum, divide_conquer 성질을 이용한다.

값이 음수가 가능하기 때문에 수많은 경우가 있는데, 아래 그림으로 그 경우들을 소개해주겠다.

 

아래 그림을 보자.

• A.leftSum으로만 이루어질 때, (여기서 leftSum은 정확히 A의 s~mid까지가 아닌, 자식노드에서 이미 최대값을 리턴해준값이라 하자. 즉, 이미 자식노드에선 계산이 끝난 것.) 
• A.sum(A전체)+B.leftSum으로 이루어질 때
• B.rightSum과 B.sum + A.rightSum도 위와 같은 방식으로 구해준다.
• 위 두 개는 모두 s 또는 e에 딱 붙어있는 경우이므로 A.rightSum + B.leftSum의 경우도 구해준다.
• 위 값들 중 최대를 리턴해준다. 이후 재귀적으로 (분할정복) 최상위 트리노드에서의 최대도 찾아준다.

위 성질이 바로 연속합 세그먼트트리에서 사용되는 것인데, 이를 이용해주면 된다.

시작 y축인 Sy를 for문으로 돌아서 탐색할 것이므로, for문 내에서 Sy는 고정된 상태에서 탐색을 시작한다고 보면 되겠다.

	for (int k = 1; k <= My; k++) {
		memset(tree, 0, sizeof(tree));
		for (int i = k; i <= My; i++) {
			for (auto j : yList[i]) {
				update(1, 1, N, j.first, j.second);
			}
			ans = max(ans, query(1, 1, N, 1, N).maxsum);
		}
	}

Sy가 고정된 상태에서 plane_sweeping을 돌면 Ey도 for문으로 처리하여 1차원에서 연속합 세그먼트트리를 이용할 수 있게 된다.

 

무슨 소리인지 잘 모르겠다면, 이중 for문 내부를 보자. 이중for문 내부에선 결국 Sy=k, Ey=i로 정해져 있으므로 y축이 고정인 상황이다. 따라서 #16993번처럼 1차원 연속합 세그먼트트리를 이용할 수 있게 되는 것이다.

 

우리는 이 작업을 O(lgN)만에 처리할 수 있으므로, 이중for문 O(N^2)*O(lgN) => 최종 시간복잡도는 O(N^2lgN)이 된다!

---

코드

// 211104 #10167 금광 Diamond V
// segtree + plane_sweeping O(N^2lgN)
// 금광세그 Standard
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> pii;
const int MAX = 3011;
const double INF = 0x3f3f3f3f;
const int LNF = 1e16;
const int MOD = 1e9 + 7;
struct Point {
	ll x, y, cost;
};
ll Mx = 1, My = 1, N, a[MAX][MAX], ans = -LNF;
pl tmpX[MAX], tmpY[MAX];
Point p[MAX];
vector<pl> yList[MAX];
struct Node {
	ll lsum, rsum, sum, maxsum;
};
Node tree[1 << 14];
Node merge(Node A, Node B) {
	return {
		max(A.lsum, A.sum + B.lsum),
		max(B.rsum, B.sum + A.rsum),
		A.sum + B.sum,
		max({ A.maxsum,B.maxsum,A.rsum + B.lsum })
	};
}
Node query(int node, int s, int e, int left, int right) {
	if (e < left || right < s)
		return { -LNF,-LNF, -LNF,-LNF };
	if (left <= s && e <= right)
		return tree[node];
	int mid = (s + e) / 2;
	return merge(query(node * 2, s, mid, left, right),
		query(node * 2 + 1, mid + 1, e, left, right));
}
void update(int node, int s, int e, int idx, ll val) {
	if (e < idx || idx < s)
		return;
	tree[node].lsum += val;
	tree[node].rsum += val;
	tree[node].sum += val;
	tree[node].maxsum += val;
	if (s != e) {
		int mid = (s + e) / 2;
		update(node * 2, s, mid, idx, val);
		update(node * 2 + 1, mid + 1, e, idx, val);
		tree[node] = merge(tree[node * 2], tree[node * 2 + 1]);
	}
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> p[i].x >> p[i].y >> p[i].cost;
		tmpX[i] = { p[i].x, i };
		tmpY[i] = { p[i].y, i };
	}
	sort(tmpX + 1, tmpX + N + 1);
	sort(tmpY + 1, tmpY + N + 1);
	for (int i = 1; i <= N; i++) {
		if (i != 1 && tmpX[i - 1].first != tmpX[i].first)
			Mx++;
		p[tmpX[i].second].x = Mx;
	}
	for (int i = 1; i <= N; i++) {
		if (i != 1 && tmpY[i - 1].first != tmpY[i].first)
			My++;
		p[tmpY[i].second].y = My;
	}
	for (int i = 1; i <= N; i++) {
		a[p[i].x][p[i].y] = p[i].cost;
		yList[p[i].y].push_back({ p[i].x, p[i].cost });
	}
	for (int k = 1; k <= My; k++) {
		memset(tree, 0, sizeof(tree));
		for (int i = k; i <= My; i++) {
			for (auto j : yList[i]) {
				update(1, 1, N, j.first, j.second);
			}
			ans = max(ans, query(1, 1, N, 1, N).maxsum);
		}
	}
	cout << ans << "\n";
}

참고로 tree 초기화를 0으로 해주지 않으면 24점밖에 못얻는다.

초기화 좀 까먹지 말자 제발 나 자신아...

---

사실 웰노운만 아니었어도 Diamond V보다 훨씬 높은 티어를 주고 싶지만...

웰노운이 아니었으면 연속합 세그먼트트리 자체를 구현을 못했을테니 못풀지 않았을까.

 

아무튼 굉~장히 어려웠던 문제.

이로써 구현력이 +1 되었다 ㅎㅎ