8155 - Postering

step 1

가로 폭이 얼마든 상관 없습니다. 전부 1로 생각합니다.

만약 모든 빌딩의 높이가 다르다면 답은 $N$입니다. 결국 높이가 같은 것들을 한번에 처리하는 것이 중요합니다.

step 2

만약 어떤 두 건물의 높이가 같고 그 사이에 있는 모든 건물이 이 건물의 높이보다 크다면 두 건물은 하나의 포스터로 처리할 수 있습니다. 이 과정은 스택을 이용해서 처리할 수 있습니다. 지금 보는 건물이 현재 스택의 top보다 크면 넣고 작으면 스택을 pop해줍니다. 만약 스택의 top과 지금 건물의 높이가 같다면 이 두 건물 사이 모든 건물이 두 건물보다 높다는 뜻입니다. 이러한 건물의 개수를 세고 $N$에서 빼주면 됩니다.

코드

#include <stdio.h>
#include <vector>
#include <algorithm>
#include<math.h>
#include<bitset>
#include<queue>
#include<stack>
using namespace std;
stack<int> s;
int main(){
    int n, i,cnt=0;
    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
        int x,y;
        scanf("%d %d", &y, &x);
        while (1) {
            if (s.size() == 0) { s.push(x); cnt++; break; }
            if (s.top() < x) { s.push(x); cnt++; break; }
            else if (s.top() > x) s.pop();
            else { s.pop(); cnt--; }
        }
    }
    printf("%d", cnt);
    return 0;
}