[BOJ/백준][Gold5] 6198 : 옥상 정원 꾸미기 (C++)

 

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

6198번: 옥상 정원 꾸미기

 

 

 

[난이도] Gold5
[유형] 스택

[풀이]
N이 8만으로 N^2 풀이는 불가능하므로 스택을 이용해서 풀어야 한다.

0번 건물의 index부터 차례로 stack에 집어넣으면서 stack에 들어있는 건물의 높이가 내림차순이 되도록 유지한다.
내림차순이 되게 하려면 스택의 top인 건물이 현재 확인중인 i번 건물보다 낮아질때까지 pop을 해줘야 한다.
pop 되어야할 i보다 낮은 k번 건물은 i-k-1 만큼의 건물을 볼수 있다. (k~i-1 까지 내림차순인 것이 보장되므로)
그러므로 pop할때마다 ans에 i-k-1만큼을 더해주면 ans가 답이다.

N이 80000이고 건물이 모두 내림차순으로 되어있다면 정답이 int 범위를 넘어가므로 long long을 사용해야 한다.

 

 

#include <cstdio>
#include <stack>
using namespace std;
int N,h[80001];
long long ans;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&h[i]);
    h[N]=2e9;
    stack<int> st;
    for(int i=0;i<=N;i++){
        while(!st.empty() && h[st.top()] <= h[i]){
                ans+=i-st.top()-1;   
                st.pop();
        }
        st.push(i);
    }
    printf("%lld",ans);
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/6198.cpp