on
[BOJ] 백준 10167. 금광 (Diamond V)
[BOJ] 백준 10167. 금광 (Diamond V)
반응형
엄청나게 높은 난이도임에도 불구하고, KOI 고등부도 아닌 중등부에 나와서 굉장히 유명해진 문제.
이 문제의 하위호환이 https://www.acmicpc.net/problem/16993 인데, 이것마저도 나에겐 굉장히 어려웠다.
위 문제를 푼 이유가 바로 '금광'을 해결하기 위해서일 정도로 이 문제는 웰노운인데,
이번 기회에 복습 겸 포스팅해보려 한다.
문제는 아래와 같다.
https://www.acmicpc.net/problem/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
라고 생각할 수 있다.
그러나 세그먼트트리 없이는 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
대략 설명을 하자면 아래와 같다.
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 #include #include #include #include #include #include #include #include #include #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 pi; typedef pair pl; typedef pair 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 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 << "
"; }
참고로 tree 초기화를 0으로 해주지 않으면 24점밖에 못얻는다.
초기화 좀 까먹지 말자 제발 나 자신아...
사실 웰노운만 아니었어도 Diamond V보다 훨씬 높은 티어를 주고 싶지만...
웰노운이 아니었으면 연속합 세그먼트트리 자체를 구현을 못했을테니 못풀지 않았을까.
아무튼 굉~장히 어려웠던 문제.
이로써 구현력이 +1 되었다 ㅎㅎ
반응형
from http://kth990303.tistory.com/204 by ccl(A) rewrite - 2021-11-04 20:00:22