[알고리즘] 백준 1725번: 히스토그램 (C++), 세그먼트 트리의 응용

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

1725번: 히스토그램

이번 문제는 유난히 어려웠다.

처음에 떠올랐던 방법은 히스토그램의 높이 중 제일 작은 것을 골라서 전체 구간의 길이와 곱해준 값을 출력해줬었다.

>> 차라리 이럴 거면 입력받을 때 최솟값을 구해서 구간과 곱해주는 건데 세그먼트 트리 문제라는 이유로 세그먼트 트리를 구한 게 멍청했다.

 

하지만, 이 방법이 안 되는 이유는 두 가지에서 떠올랐다.

1. 어떤 높이가 0인 경우 >> 그러면 답이 0이 나오게 되는데 이건 말이 안 된다.
2. 아래 그림에서 설명

내가 생각한 방법이라면 여기선 답이 5가 나온다. 하지만, 상식적으로 생각해보면 이 히스토그램에선 index [4, 5]에서 넓이 10이 발생하기 때문에 내 발상은 잘못됐다.

---

[솔루션]

(참고: https://www.crocus.co.kr/707)

즉, 그림으로 다시 한번 설명하면

이 경우에서 그치지 않고,

제일 작은 높이를 제외한 직사각형은 좌우로 생길 수 있음을 인지 한다면

위 두 가지도 따질 수 있다.

허나, 여기서 그치지 않고, 또 각 직사각형에서 최솟값을 유발하는 높이를 제외한 다음에 또 좌우로 만들어지는 직사각형의 넓이를 구해나간다면 최댓값을 찾을 수 있다.

>> 범위를 줄여나가면서 어떠한 행위를 반복하는 방법은 어디서 많이 보았다.

>> 분할 정복이다.

 

이 분할 정복을 수도 코드로 나타내 보자.

// 당연하게도 함수 콜을 할 때는 처음부터 끝까지의 범위를 주어야 한다.

getMax(int start, int end) {
	int m = 최솟값을 유발하는 높이의 인덱스;

	최대 면적 = (end - start + 1) * arr[m];

	if (start <= m - 1) {
		왼쪽에서 나오는 최대 면적 = getMax(start, m - 1);
		if (최대 면적 < 왼쪽에서 나오는 최대 면적) {
			최대 면적 = 왼쪽에서 나오는 최대 면적;
		}
	}

	if (end >= m + 1) {
		오른쪽에서 나오는 최대 면적 = getMax(m + 1, end);
		if (최대 면적 < 오른쪽에서 나오는 최대 면적) {
			최대 면적 = 오른쪽에서 나오는 최대 면적;
		}
	}

	return 최대 면적;
}

변수 m에서 높이가 아닌 높이를 가지는 인덱스를 가져오는 이유는 범위를 알려주기 위한 분할 정복을 위해서다.

 

이제 최솟값을 유발하는 인덱스를 어떻게 가져올 것인지 생각해보자.

>> start와 end 사이에 최솟값을 유발하는 인덱스

>> 이제야 세그먼트 트리가 떠오른다.

최솟값 인덱스 세그먼트 트리는 저번 문제에서 사용했으므로 그 링크를 가져오겠다.

https://draw-code-boy.tistory.com/177

[자료구조] 백준 14428번: 수열과 쿼리 16 (C++), 인덱스 세그 트리

 

그럼 전체 코드를 나타내 보면 이렇게 나온다.

[AC 코드]

#include <iostream>
#include <cmath>
#define MAX (100000 + 1)
#define INF 987654321
#define ll long long
using namespace std;

ll sgTree[MAX * 4];
ll arr[MAX];
int n;

int minIdx(int a, int b) {
	return arr[a] < arr[b] ? a : b;
	//if (arr[a] == arr[b]) return min(a, b);
}

int sgInit(int start, int end, int node) {
	if (start == end) {
		return sgTree[node] = start;
	}

	int mid = (start + end) >> 1;
	return sgTree[node] = minIdx(sgInit(start, mid, node * 2), sgInit(mid + 1, end, node * 2 + 1));
}

int query(int start, int end, int node, int left, int right) {
	if (left > end || right < start) return 0;

	if (left <= start && end <= right) return sgTree[node];

	int mid = (start + end) >> 1;
	return minIdx(query(start, mid, node * 2, left, right), query(mid + 1, end, node * 2 + 1, left, right));
}

ll getMax(int start, int end) {
	int m = query(1, n, 1, start, end);

	ll area = (ll)(end - start + 1) * (ll)arr[m];

	if (start <= m - 1) {
		ll temp = getMax(start, m - 1);
		if (area < temp) {
			area = temp;
		}
	}

	if (end >= m + 1) {
		ll temp = getMax(m + 1, end);
		if (area < temp) {
			area = temp;
		}
	}

	return area;
}

int main() {
	arr[0] = INF;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	sgInit(1, n, 1);

	cout << getMax(1, n);
	return 0;
}

---

[느낀 점]

최근 들어 플레티넘에 도전하느라 '알고리즘은 기법이다.'라는 마인드를 까먹고 살았던 거 같다.

역시 근본적으로 1. 알고리즘 2. 문제가 아니라 문제를 풀기 위해 필요한 것이 알고리즘임을 또다시 리마인드 시킨다.

그리고, 어쩌다 보니 이번 문제는 세그먼트 트리와 분할 정복의 복합 문제였다.

다시 풀어보면 재밌을 문제 같다.

---

+잘못된 발상으로 비롯된 코드는 아래에 첨부해 두었다. 추후에 솔루션을 알고 나서 기존의 코드를 뜯어고쳐서 해보려 했지만 틀 자체가 틀려서 갈아엎어야 한다.

 

[잘못된 발상으로 비롯된 코드]

#include <iostream>
#define MAX (100000 + 1)
#define ll long long
using namespace std;

int arr[MAX];
int sgTree[MAX * 4];
int n;
int maxValue = 0;

int sgInit(int start, int end, int node) {
	if (start == end) {
		return sgTree[node] = arr[start];
	}
	int mid = (start + end) / 2;
	return sgTree[node] = min(sgInit(start, mid, node * 2), 
		sgInit(mid + 1, end, node * 2 + 1));
}

void cal(int start, int end, int node) {
	int result = (end - start + 1) * sgTree[node];
	maxValue = max(result, maxValue);
	if (start == end) {
		return;
	}
	int mid = (start + end) / 2;
	cal(start, mid, node * 2);
	cal(mid + 1, end, node * 2 + 1);
	return;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	sgInit(1, n, 1);
	
	cal(1, n, 1);
	cout << maxValue;
	return 0;
}