풀이
분할정복 + 세그트리로 푸는 풀이도 있다.
근데 복잡하다.
그리디하게 생각해보자.
순차적으로 돌면서 현재 막대의 높이가 이전 막대보다 작아졌다면
이전 막대는 현재 막대 이후로 고려할 필요가 없어진다.
넓이를 구해보자.
코드
#include <stdio.h>
#include <stack>
#include <algorithm>
using namespace std;
typedef long long ll;
struct ABC { int idx, hgt; };
int n, h;
ll ans;
stack<ABC> stk;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &h);
while (!stk.empty() && stk.top().hgt > h) {
auto prv = stk.top(); stk.pop();
ans = max(ans, (ll)(stk.empty() ? i : i - stk.top().idx - 1) * prv.hgt);
}
stk.push({ i, h });
}
while (!stk.empty()) {
auto prv = stk.top(); stk.pop();
ans = max(ans, (ll)(stk.empty() ? n : n - stk.top().idx - 1) * prv.hgt);
}
printf("%lld\n", ans);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge