# [Gold IV] 스카이라인 쉬운거 #### [문제링크](https://www.acmicpc.net/problem/1863) ## 문제 설명 <p>도시에서 태양이 질 때에 보이는 건물들의 윤곽을 스카이라인이라고 한다. 스카이라인만을 보고서 도시에 세워진 건물이 몇 채인지 알아 낼 수 있을까? 건물은 모두 직사각형 모양으로 밋밋하게 생겼다고 가정한다.</p> <p>정확히 건물이 몇 개 있는지 알아내는 것은 대부분의 경우에 불가능하고, 건물이 최소한 몇 채 인지 알아내는 것은 가능해 보인다. 이를 알아내는 프로그램을 작성해 보자.</p> ## 입력 <p>첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 번째 지점의 x좌표는 항상 1이다.</p> ## 출력 <p>첫 줄에 최소 건물 개수를 출력한다.</p> ## 풀이 #### 이 문제는 건물의 실루엣의 y좌표가 주어지고, 최소 건물 수를 찾는 문제입니다. #### 실루엣을 실제로 그려보고 맨 아래층부터 한층씩 제거하는 방법으로 풀었습니다. #### 이를 스택으로 구현하여 풀어 보면 모노톤 스택이라는 것을 알 수 있습니다. ```c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; int cnt=0; stack<int> stk; while(n--) { int x, y; cin >> x >> y; while(!stk.empty() && stk.top()>y) stk.pop(); // 스택에서 현재 건물보다 큰 최신 건물들 제거 if(y>0 && (stk.empty() || stk.top()<y)) { // 건물 넣고 cnt+1 stk.push(y); cnt++; } } cout << cnt; } ```