Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- 스파르타코딩클럽 #spartacodingclub #누구나큰일낼수있어
- 김영한님
- 자바의 정석 기초편
- 팀300
- 백준 1992번 풀이
- 백준
- 스프링 시큐리티 구조
- 가상 채팅서버
- 스프링 핵심원리 기본편
- C++
- 전문가를 위한 스프링
- 백준 2630번
- 스파르타코딩클럽
- 1시간 만에 끝내는 직장인 코딩 용어
- SQL
- 스프링 입문을 위한 자바 객체 지향의 원리와 이해
- 백준 1992번
- 객체지향의 사실과 오해
- 스프링 MVC 2편
- 스프링심화반
- 스프링
- thymeleaf
- 전문가를 위한 스프링5
- 타임리프
- JPA
- 누구나큰일낼수있어
- 알고리즘
- 백준 #N과 M(4) #백트래킹
- 채팅서버 설계
- spartacodingclub
Archives
- Today
- Total
민우의 코딩노트
6549번 히스토그램에서 가장 큰 직사각형 - C++ 본문
[문제]
https://www.acmicpc.net/problem/6549
[풀이]
1. 스택을 이용한 방법
최대 넓이를 구하기 위해서 스택의 top에 존재하는 높이 값이 현재 높이값보다 크거나 같을때까지 스택을 탐색하여 최대 넓이를 구한다.
스택에는 (삭제할때의 idx, 높이)를 저장하고, 스택에 저장하면 된다.
주의할 점은 0~n 까지 탐색할 경우 마지막에 넣은 높이의 넓이를 구할수 없으므로, S.empty()를 조사하여 최대 넓이를 구하도록 한다.
[코드]
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
while(1){
int n;
cin >> n;
if(n == 0) break;
long long ans = 0LL;
stack<pair<int,int>> S;
for(int i=0; i<n; i++){
int h;
int idx = i;
cin >> h;
while(!S.empty() && S.top().second >= h){
ans = max(ans, 1LL * (i-S.top().first) * S.top().second);
idx = S.top().first;
S.pop();
}
S.push({idx, h});
}
while(!S.empty()){
ans = max(ans, 1LL*(n-S.top().first)*S.top().second);
S.pop();
}
cout << ans << "\n";
}
}
'Algorithm > BOJ' 카테고리의 다른 글
2164번 카드2 - C++ (0) | 2022.07.25 |
---|---|
18258번 큐 2 - C++ (0) | 2022.07.25 |
3015번 오아시스 재결합 - C++ (0) | 2022.07.24 |
10773번 제로 - C++ (0) | 2022.07.16 |
10828번 스택 - C++ (0) | 2022.07.16 |