반응형
https://www.acmicpc.net/problem/1725
1725번: 히스토그램
첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은
www.acmicpc.net
[ 문제풀이 ]
다음과 같은 순서대로 문제를 풀어주시면 쉽게 답을 구할 수 있습니다.
1. push 하려는 막대의 높이가 s.top() 인덱스의 막대 높이보다 크거나 같다면 계속해서 스택을 쌓습니다.
2. 만약 push 하려는 막대의 높이가 s.top() 인덱스의 막대 높이보다 작다면 s.top()이 push 하려는 막대 높이보다 커질 때까지 s.pop()을 해줍니다.
3. s.pop()을 할 때마다 직사각형의 넓이를 구하고 최댓값을 저장합니다.
다음 글은 세그먼트 트리와 분할 정복을 통해 문제를 푸는 방법입니다.
https://rudalsd.tistory.com/88?category=1064612
[ 소스 코드 ]
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 31 | #include<iostream> #include<stack> using namespace std; int N; int arr[100005]; int ans; int main() { stack<int> s; s.push(0); scanf("%d", &N); for (int i = 1; i <= N; i++) { scanf("%d", &arr[i]); } for (int i = 1; i <= N + 1; i++) { while (!s.empty() && arr[i] < arr[s.top()]) { int cur = s.top(); s.pop(); int W = arr[cur] * (i - s.top() - 1); ans = max(ans, W); } s.push(i); } printf("%d", ans); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 10026번 - 적록색약 (C++) (0) | 2022.08.05 |
|---|---|
| [ 백준 ] 11438번 - LCA 2 (C++) (0) | 2022.08.04 |
| [ 백준 ] 6549번 - 히스토그램에서 가장 큰 직사각형 (C++) (0) | 2022.08.02 |
| [ 백준 ] 1629번 - 곱셈 (C++) (0) | 2022.08.01 |
| [ 백준 ] 11725번 - 트리의 부모 찾기 (C++) (0) | 2022.07.31 |