https://www.acmicpc.net/problem/16993
16993번: 연속합과 쿼리
길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j : Ai, Ai+1, ..., Aj에서 가장 큰 연속합을 출력한다. (1 ≤ i ≤ j ≤ N) 수열의 인덱스는 1부터 시작
www.acmicpc.net
"금광 세그" 라고 불릴 정도의 웰노운 문제지만 어렵습니다. ㅠㅠ
이 문제는 "금광" 문제를 풀기 위한 워밍업 문제이며, 이 문제를 푸셨다면 금광 문제에 도전하시는 것도 좋습니다.
금광 세그는 구간에서 가장 큰 연속합을 구하는 문제입니다.
세그먼트 트리를 활용할 수 있으며, 두 개의 노드를 병합했을 때,
[왼쪽 노드의 최대, 오른쪽 노드의 최대, 두 노드의 중간]
이 정도가 답이 될 수 있습니다.
이를 구하기 위해 세그먼트 트리에는 다음과 같은 값을 저장합니다.
- l: 왼쪽 하위노드 (leftNode)의 최대
- r: 오른쪽 하위노드 (rightNode)의 최대
- max: 현재 노드의 최대
- sum: 현재 노드의 전체 합
이 값들을 구하는 방법은
- l: max(leftNode.l, leftNode.sum + rightNode.l)
- r: max(rightNode.r, rightNode.sum + leftNode.r)
- max: max(leftNode.max, rightNode.max, leftNode.r + rightNode.l)
- sum: leftNode.sum + rightNode.sum
이러면 전체 구간에서의 max를 구할 수 있습니다.
해당 식을 알고 있다면 쉽게 풀리는 문제지만, 처음보는 입장에서 이해하기는 어려웠습니다.
비슷한 문제로 update가 추가된 문제와 좌표압축이 추가된 금광 문제도 함께 공유드리고, 마무리하겠습니다.
https://www.acmicpc.net/problem/15561
15561번: 구간 합 최대? 2
첫 번째 줄에 정수 N과 Q, U, V가 입력된다. (1 ≤ N, Q ≤ 105, - 5 ≤ U, V ≤ 5) 두 번째 줄에 정수 K1, K2, ..., KN이 주어진다. (-102 ≤ Ki ≤ 102) 세 번째 줄부터 쿼리가
www.acmicpc.net
https://www.acmicpc.net/problem/10167
10167번: 금광
첫 줄에는 금광들의 개수 N (1 ≤ N ≤ 3,000)이 주어진다. 이어지는 N개의 줄 각각에는 금광의 좌표 (x, y)를 나타내는 음이 아닌 두 정수 x와 y(0 ≤ x, y ≤ 109), 그리고 금광을 개발하면 얻게 되는 이
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
#include <iostream>
#include <algorithm>
#define MAX 100001
using namespace std;
typedef struct Node {
int l;
int r;
int max;
int sum;
}Node;
Node tree[MAX * 4];
int list[MAX];
int N, M;
Node init(int node, int s, int e) {
if (s == e) {
return tree[node] = { list[s], list[s], list[s], list[s] };
}
int m = (s + e) / 2;
Node leftNode = init(node * 2, s, m);
Node rightNode = init(node * 2 + 1, m + 1, e);
return tree[node] = { max(leftNode.l, leftNode.sum + rightNode.l), max(rightNode.r, leftNode.r + rightNode.sum), max(max(leftNode.max, rightNode.max), leftNode.r + rightNode.l), leftNode.sum + rightNode.sum };
}
Node query(int node, int s, int e, int l, int r) {
if (s > r || l > e) return { (int)-1e9, (int)-1e9, (int)-1e9, 0 };
if (l <= s && e <= r) return tree[node];
int m = (s + e) / 2;
Node leftNode = query(node * 2, s, m, l, r);
Node rightNode = query(node * 2 + 1, m + 1, e, l, r);
return { max(leftNode.l, leftNode.sum + rightNode.l), max(rightNode.r, leftNode.r + rightNode.sum), max(max(leftNode.max, rightNode.max), leftNode.r + rightNode.l), leftNode.sum + rightNode.sum };
}
void func() {
int l, r;
cin >> M;
while (M--) {
cin >> l >> r;
cout << query(1, 1, N, l, r).max << '\n';
}
}
void input() {
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> list[i];
}
init(1, 1, N);
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > SegmentTree' 카테고리의 다른 글
| boj 12895 화려한 마을 (0) | 2022.09.07 |
|---|---|
| boj 10167 금광 (0) | 2022.09.02 |
| boj 12846 무서운 아르바이트 (0) | 2022.08.19 |
| boj 1849 순열 (0) | 2021.09.08 |
| boj 14719 빗물 (0) | 2021.03.15 |