[알고리즘] 백준 6549 히스토그램 // 스택 심화, 암기..

https://www.acmicpc.net/problem/6549

 

* 풀이

• 스택문제는 오름차순, 내림차순, 같은경우를 나눠생각
• 이중에서 계산해야 되는 걸 골라야함!
• 이문제는 내림차 일때, 기존의 막대들이 확장불가 ( 확정) -> 계산을 드가면됨.

• 이때, 패딩을 0으로 줘서 마지막도 강제 내림차로만들고 i = n+1 까지 돌려서, 마지막에 자동계산토록 함 

• 특이한점은 pop을 한후에 전전 막대의 idx 차이를 너비로 사용

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, arr[100000+4];

// < 값, idx >

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);

   while(1) {
      cin>>n;
      if(n==0) return 0;

      stack<pair<ll,ll>> s; // tc문제는 초기화 주의
      ll ret=0;
      memset(arr,0,sizeof(arr));

      for (int i = 1; i <= n; i++) cin >> arr[i];

      s.push({0,0});
      for(int i=1;i<=n+1;++i) { // n+1까지!
         // 내림차순 -> 확정 -> 계산
         while(s.size() && s.top().first > arr[i]) {
            int h = s.top().first;
            s.pop();
            ret= max(ret, (i-s.top().second-1) * h); // 밑변 * 높이
         }
         // 오름차순, 같은경우 -> 단순 push
         s.push({arr[i],i});
      }
      cout<<ret<<"\n";
   }

   
   return 0;
}