이 영역을 누르면 첫 페이지로 이동
자라자 블로그의 첫 페이지로 이동

자라자

페이지 맨 위로 올라가기

백준 6549 히스토그램에서 가장 큰 직사각형 풀이 c++

자라자

백준 6549 히스토그램에서 가장 큰 직사각형 풀이 c++

  • 2022.01.25 21:07
  • PS/BOJ

백준로고

[문제 링크]

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

댓글

댓글을 사용할 수 없습니다.

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • 백준 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
다른 글 더 둘러보기

정보

자라자 블로그의 첫 페이지로 이동

자라자

  • 자라자의 첫 페이지로 이동

검색

메뉴

  • 🏠 HOME
  • 💡 ABOUT
  • 💻 GITHUB

카테고리

  • 분류 전체보기 (91)
    • Tech Note (3)
    • Dev Log (11)
    • Study Log (11)
    • Settings (3)
    • PS (53)
      • Programmers (21)
      • BOJ (32)
    • Diary (10)

인기 글

공지사항

태그

  • 리액트
  • ㅣ
  • 공식문서읽기

정보

자라자의 자라자

자라자

자라자

블로그 구독하기

  • 구독하기
  • RSS 피드

방문자

  • 전체 방문자
  • 오늘
  • 어제

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
Powered by Tistory / Kakao. © 자라자. Designed by Fraccino.

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.