코드 복사/붙여넣기 하는 당신이 아름답습니다.

14727 : 퍼즐 자르기

풀이

분할정복 + 세그트리로 푸는 풀이도 있다.

근데 복잡하다.

그리디하게 생각해보자.

순차적으로 돌면서 현재 막대의 높이가 이전 막대보다 작아졌다면

이전 막대는 현재 막대 이후로 고려할 필요가 없어진다.

넓이를 구해보자.

코드

#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

wookje.kwon's profile image

wookje.kwon

2017-09-24 01:10

Read more posts by this author