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

리뷰

 

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

히스토그램에서 가장 큰 직사각형의 면적을 찾는 문제와 동일한 풀이 방식을 가진 문제

 

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

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

 

 

전역 변수

• N : n의 최대값을 명시하기 위한 정수형 상수 변수
• n : 퍼즐 조각의 개수를 저장하기 위한 정수형 변수
• lst : 퍼즐 조각의 높이를 저장하기 위한 정수형 배열
• tree : 세그먼트 트리 정보를 저장하기 위한 정수형 배열

 

함수

1. build

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

 

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

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

 

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, right에 저장해 준다.
6. 만약 left가 -1이라면 right를, right가 -1이라면 left를 리턴해 준다.
7. 둘 다 -1이 아닐 경우 lst 배열에서 left, right 중 더 작은 값을 갖는 인덱스를 리턴해 준다.

 

3. query

ll query(int s, int e)

 

구간에서 가장 큰 직사각형의 넓이를 구하기 위한 함수

1. 매개 변수로 탐색 범위 s, e를 전달받는다.
2. 기저 조건으로 만약 s가 e보다 커졌을 경우 0을 리턴해 준다.
3. 정수형 변수 minIndex에 getIndex함수를 통해 세그먼트 트리에서 s, e범위 내의 최소값을 가진 인덱스를 저장한다.
4. lst의 minIndex값과 탐색 범위를 곱한 값을 정수형 변수 all에 저장해 준다.
5. 이후 minIndex를 기준으로 좌, 우 재귀탐색을 진행하며 각각의 리턴값을 left, right에 저장해 준다.
6. all, left, right 중 가장 큰 값을 리턴해 준다.

 

문제풀이

1. n값을 입력 받아주고, n개의 퍼즐 높이 정보를 lst배열에 저장해 준다.
2. build함수를 통해 세그먼트 트리 정보를 초기화 해준다.
3. query함수를 통해 직사각형의 최대 값을 찾은 후 출력해 준다.

 

트러블 슈팅

1. 오랜만에 다시 풀어보는 유형이라 getIndex와 query함수 구현이 다소 헷갈린 부분이 있었다.

 

참고 사항

• query함수는 세그먼트 트리 정보와 직접적으로 연관이 없기에 매개변수로 node를 전달하지 않아도 된다.
• left와 right를 탐색할 때엔 각각 minIndex에서 -1 혹은 +1을 해준 값을 매개변수로 전달해 주어야 한다.

 

정답 코드

#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);
		int left = tree[node * 2];
		int right = tree[node * 2 + 1];
		tree[node] = lst[left] <= lst[right] ? left : right;
	}
}

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);
}