백준 6549 히스토그램에서 가장 큰 직사각형 풀이 c++
[문제 링크]
https://www.acmicpc.net/problem/6549
[입출력 예]
입력 | 출력 |
---|---|
7 2 1 4 5 1 3 3 4 1000 1000 1000 0 |
8 4000 |
[소스코드]
// Authored by : haneulkimdev // Co-authored by : BaaaaaaaaaaarkingDog // http://boj.kr/d98aedfde0e444509de83f1a21c8ef7e #include <bits/stdc++.h> using namespace std; #define X first #define Y second int main(void) { ios::sync_with_stdio(0); cin.tie(0); while (true) { int n; cin >> n; if (n == 0) break; stack<pair<int, int>> S; long long ans = 0; for (int i = 0; i < n; i++) { int h; cin >> h; int idx = i; while (!S.empty() && S.top().X >= h) {//스택이 비거나 h보다 더 낮은 top이 나올때까지. ans = max(ans, 1LL * (i - S.top().Y) * S.top().X); idx = S.top().Y; S.pop(); } S.push({h, idx}); //top보다 더 높은 h를 만나면 쌓아둔다. } while (!S.empty()) { ans = max(ans, 1LL * (n - S.top().Y) * S.top().X); S.pop(); } cout << ans << '\n'; } } // 풀이 // 수열이 증가할 때 : 스택에 쌓는다. // 수열이 감소할 때 : 스택이 비거나 현재 높이보다 낮을 때까지 뽑는다. // 끝까지 뽑는 게 아니라 현재높이 전까지만 뽑으면 되는 이유는 현재 높이가 새로운 증가수열로 커버해줄 수 있기 때문이다. // 증가수열만 스택 안에 보관되어있으므로, 거리를 곱해주면서 직사각형 넓이를 갱신하면 된다. // 바로 전 top은 가로길이가 1이고 그 높이만큼 온전히 보장된다. // 전전 top은 바로 전의 top이 더 크기때문에 X2(거리)를 해도 감당이 된다. // 모든 작업이 끝나고 스택을 비워주면서 계산을 꼼꼼하게 한다.
'PS > BOJ' 카테고리의 다른 글
백준 2164 카드2 c++ (0) | 2022.02.01 |
---|---|
백준 10845 큐,큐2 c++ (0) | 2022.02.01 |
백준 3015 오아시스 재결합 c++ (0) | 2022.01.25 |
백준 17298 오큰수 c++ (0) | 2022.01.13 |
백준 6918 옥상 정원 꾸미기 c++ (0) | 2022.01.13 |
댓글
이 글 공유하기
다른 글
-
백준 2164 카드2 c++
백준 2164 카드2 c++
2022.02.01 -
백준 10845 큐,큐2 c++
백준 10845 큐,큐2 c++
2022.02.01 -
백준 3015 오아시스 재결합 c++
백준 3015 오아시스 재결합 c++
2022.01.25 -
백준 17298 오큰수 c++
백준 17298 오큰수 c++
2022.01.13
댓글을 사용할 수 없습니다.