오늘은 오랫동안 묵혀두었던 P5 문제이다.
주어진 히스토그램에서 가장 큰 직사각형의 넓이를 구하는 문제이다.
아이디어가 하나 떠오르자마자 바로 풀려서 생각보다 놀랐다.
오늘은 운수 좋은 날...?
문제링크
https://www.acmicpc.net/problem/6549
설명
일단 나는 이 문제를 스택으로 풀었다.
이 문제의 포인트는 어떠한 구간에서 최솟값이 넓이를 결정한다는 것과 자신의 index를 기준으로 좌우를 모두 생각해야 한다는 것이다.
예를 들어 index = 1, value = 4의 수가 있다고 가정하겠다.
또한 2가지 배열을 만들어 줄건데,
rans배열은 자신보다 더 큰 index를 가진 수들만 고려한 넓이이고
lans 배열은 자신보다 더 작은 index를 가진 수들만 고려한 넓이이다.
우선 rans배열을 보자.
위 정보를 스택에 넣어놓고 자신보다 큰 index를 가지는 수들 중, 더 작은 value를 가진 수가 들어올 때까지 for문을 돌린다.
자신보다 작은 value를 가진 값이 들어온다면 (index = 5, value = 3이라고 하자), rans[1]에 4 * (5 - 1)의 값인 16을 저장한다.
rans[3] = 16이 되는 이유는 index = 2, 3, 4일 때는 자신보다 더 큰 수가 들어와 높이가 4인 직사각형의 크기를 늘릴 수 있지만, index = 5일 때는 자신보다 작은 수가 들어와 높이가 4인 직사각형을 만들 수 없기 때문이다.
위 과정에 따르면
rans배열의 값은 index 순서대로 16 5 8 6 3이 될 것이다.
이제 lans배열을 생각해보자.
위 과정을 반대로 생각하면 된다.
위 그림에서 index = 5, value = 3인 수는 왼쪽으로 가면 넓이 15인 직사각형을 만들 수 있지만 rans배열에서는 자신보다 큰 index를 가진 수들만 고려하므로 3의 값을 가진다.
lans배열에는 자신보다 index가 작은 수들을 가지고 만들 수 있는 가장 큰 직사각형의 넓이를 저장한다.
위 그림으로 따지면 lans[5] = 15가 되고 lans[1] = 4가 된다.
이제 두 배열을 합쳐서 고려하면 된다.
rans배열과 lans배열을 합친 값에서 자기 자신의 값을 뺀 값들 중 가장 큰 수가 위 히스토그램에서 만들 수 있는 가장 큰 직사각형의 넓이가 된다.
이를 식으로 나타내면 다음과 같다.
ans[i] = rans[i] + lans[i] - arr[i];
// rans[i] += lans[i] - arr[i];로 하면 메모리를 조금이라도 아낄 수 있다.
똑같은 내용이지만 수의 범위가 작은 다른 문제가 있다.
한 구간의 최솟값이 중요하다고 생각해서 맨 처음 세그먼트 트리를 이용하려다가 아이디어 적용에 실패해서 스택을 이용하는 아이디어로 문제를 풀었는데 다음에는 세그먼트 트리를 이용해서 그 문제를 풀어봐야겠다.
코드
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
struct node {
long long val;
int idx;
};
int n;
long long arr[100000], rans[100000], lans[100000], ans[100000];
void input()
{
for (int i = 0; i < n; i++)
cin >> arr[i];
}
void rsol()
{
stack<node> s;
for (int i = 0; i < n; i++)
{
while (!s.empty() && s.top().val > arr[i])
{
long long val = s.top().val;
int idx = s.top().idx;
rans[idx] = (i - idx) * val;
s.pop();
continue;
}
s.push({ arr[i], i });
}
int midx = s.top().idx + 1;
while (!s.empty())
{
long long val = s.top().val;
int idx = s.top().idx;
rans[idx] = (midx - idx) * val;
s.pop();
}
}
void lsol()
{
stack<node> s;
for (int i = n - 1; i >= 0; i--)
{
while (!s.empty() && s.top().val > arr[i])
{
long long val = s.top().val;
int idx = s.top().idx;
lans[idx] = (idx - i) * val;
s.pop();
continue;
}
s.push({ arr[i], i });
}
int midx = s.top().idx - 1;
while (!s.empty())
{
long long val = s.top().val;
int idx = s.top().idx;
lans[idx] = (idx - midx) * val;
s.pop();
}
}
void solution()
{
rsol(); // 자기보다 큰 idx만 고려할 때
lsol(); // 자기보다 작은 idx만 고려할 때
for (int i = 0; i < n; i++)
ans[i] = lans[i] + rans[i] - arr[i];
cout << *max_element(ans, ans + n) << '\n';
}
void solve()
{
while (1)
{
cin >> n;
if (n == 0)
break;
input();
solution();
}
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
return 0;
}