[P5] 백준 12846번 무서운 아르바이트 C++ 세그먼트 트리

리뷰

 

세그먼트 트리에 수열의 값 중 가장 작은 값의 인덱스를 저장하고, 이를 활용하여 재귀를 통해 구간의 최대 값을 구하는 문제, 유사한 문제가 상당히 많아 하나만 풀어도 딸려오는 문제가 많다.

 

[P5] 백준 1725번 히스토그램 C++ 세그먼트 트리

[P5] 백준 1725번 히스토그램 C++ 세그먼트 트리

 

 

[P5] 백준 6549번 히스토그램에서 가장 큰 직사각형 C++ 세그먼트 트리, 분할 정복

[P5] 백준 6549번 히스토그램에서 가장 큰 직사각형 C++ 세그먼트 트리, 분할 정복

 

[P5] 백준 14727번 퍼즐 자르기 C++ 세그먼트 트리

[P5] 백준 14727번 퍼즐 자르기 C++ 세그먼트 트리

 

 

전역 변수

• N : n의 최대값을 저장하기 위한 정수형 상수 변수
• n : 수열의 크기를 저장할 정수형 변수
• lst : 수열의 값을 저장하기 위한 정수형 배열
• tree : 세그먼트 트리 정보를 저장하기 위한 정수형 배열

 

함수

1. build

void build(int node, int s, int e)

 

세그먼트 트리 정보를 초기화 하기 위한 함수

1. 매개 변수로 노드 정보 node, 탐색 범위 s, e를 전달받는다.
2. 기저 조건으로 리프 노드에 도달했을 경우 현재 노드에 탐색 인덱스를 저장해 준다.
3. 리프노드가 아닐 경우 좌, 우 자식 노드로 재귀를 진행해 준다.
4. 재귀를 빠져나오며 현재 노드의 값에 자식 노드의 인덱스가 lst배열에서 더 작은 값인 인덱스를 저장한다.

 

2. getIndex

int getIndex(int node, int s, int e, int L, int R)

 

구간의 최소값을 가지는 인덱스를 뽑아내기 위한 함수

1. 매개 변수로 노드 정보 node, 탐색 범위 s, e, 최소값의 인덱스를 뽑을 범위 L, R을 전달받는다.
2. 첫 번째 기저 조건으로 만약 범위를 벗어난 경우 -1을 리턴해 준다.
3. 두 번째 기저 조건으로 탐색 범위가 인덱스를 뽑을 범위에 포함된다면 현재 노드값을 리턴한다.
4. 기저 조건에 해당하지 않을 경우 좌, 우 노드로 재귀 탐색을 진행해 준다.
5. 재귀를 빠져나온 뒤 left가 -1이라면 right를, right가 -1이라면 left를 리턴해 준다.
6. 둘 다 -1이 아니라면 lst배열에서 더 작은 값을 가지는 인덱스를 리턴해 준다.

 

3. query

ll query(int s, int e)

 

재귀를 통해 최대 이익을 반환하기 위한 함수

1. 기저 조건으로 s가 e보다 커졌을 경우 0을 리턴해 준다.
2. getIndex함수를 통해 s, e범위에서 가장 작은 값의 인덱스를 정수형 변수 minIndex에 저장해 준다.
3. 변수 all에 lst배열에서 minIndex의 값에 탐색 범위를 곱한 값을 저장해 준다.
4. 이후 s부터 minIndex - 1, minIndex + 1부터 e까지 재귀를 진행하고 각각 리턴받은 값을 left, right에 저장한다.
5. all, left, right 중 가장 큰 값을 리턴해 준다.

 

문제풀이

1. n값을 입력 받고, n개의 요소를 입력 받아 lst배열에 저장해 준다.
2. build함수를 통해 세그먼트 트리 정보를 초기화 해준다.
3. query함수를 호출하고 전달 받은 리턴값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

동일한 문제가 많은 꿀통 문제이다. 잊을만 하면 한 문제씩 선택하여 풀어주는걸 추천한다.

 

 

정답 코드

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

const int N = 100000;
int n;
ll lst[N];
int tree[N * 4];

void build(int node, int s, int e) {
	if (s == e) tree[node] = s;
	else {
		int mid = (s + e) / 2;
		build(node * 2, s, mid);
		build(node * 2 + 1, mid + 1, e);
		tree[node] = lst[tree[node * 2]] <= lst[tree[node * 2 + 1]] ? tree[node * 2] : tree[node * 2 + 1];
	}
}

int getIndex(int node, int s, int e, int L, int R) {
	if (R < s || e < L) return -1;
	if (L <= s && e <= R) return tree[node];
	int mid = (s + e) / 2;
	int left = getIndex(node * 2, s, mid, L, R);
	int right = getIndex(node * 2 + 1, mid + 1, e, L, R);
	if (left == -1) return right;
	if (right == -1) return left;
	return lst[left] <= lst[right] ? left : right;
}

ll query(int s, int e) {
	if (s > e) return 0;
	int minIndex = getIndex(1, 0, n - 1, s, e);
	ll all = lst[minIndex] * (e - s + 1);
	ll left = query(s, minIndex - 1);
	ll right = query(minIndex + 1, e);
	return max({ all, left, right });
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; ++i) cin >> lst[i];
	build(1, 0, n - 1);
	cout << query(0, n - 1);
}