백준(C, C++)/골드

백준 1863: 스카이라인 쉬운거 [C/C++]

치킨먹고싶어요 2022. 7. 13. 14:39

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

 

1863번: 스카이라인 쉬운거

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫

www.acmicpc.net

#include <iostream>
#include <stack>
using namespace std;
int n, t, ans;
int m[55555];
static const auto fastio = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
int main() {
    cin >> n;
    for (int i = 0; i < n; i++cin >> t >> m[i];
    stack<int> s;
    for (int i = 0; i < n; i++) {
        if (m[i] != 0) { // 높이가 0이 아닐 때
            bool exist = false;
            while (!s.empty()) {
                if (s.top() == m[i]) { // 동일한 높이가 스택에 존재한다면 
                    exist = true;
                    break;
                }
                if (s.top() < m[i]) { // 스택에 있는 값 보다 크다면
                    break;
                }
                s.pop();
            }
            if (exist) continue;
            else { // 스택이 다 비워졌거나, 스택에 있는 값보다 크다면
                s.push(m[i]);
                ans++;
            }
        }
        else while (!s.empty()) s.pop(); // 높이가 0이면 스택을 비운다.
    }    
    cout << ans;
    return 0;
}
 
 
 

스택을 이용하는 문제입니다.

규칙을 찾아 스택을 활용하면 풀 수 있습니다.