201 words
1 minutes
[BOJ] 스카이라인 쉬운거
TimeLimit | MemoryLimit | Condition | TAG |
---|---|---|---|
2s | 128MB | (1 ≤ N ≤ 50,000) | Stack |
음.. 대놓고 그냥 스택 문제여서 잘 풀었던 것 같다.
이거는 스택으로 올라가는 놈들 처리만 해주면 된다!
정답 코드
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
using ll = unsigned long long;
int inf = 1e9+7;
int n;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
vector<int> stack;
cin >> n;
int s, h;
int result = 0;
for(int i = 0; i < n; i++){
cin >> s >> h;
while(!stack.empty() && stack.back() == 0)stack.pop_back();
if(stack.empty()){
stack.push_back(h);
}
else{
if(stack.back() > h){
while(!stack.empty() && stack.back() > h){
stack.pop_back();
result++;
}
if(stack.empty() || stack.back() != h) stack.push_back(h);
}else{
stack.push_back(h);
}
}
}
while(!stack.empty() && stack.back() == 0)stack.pop_back();
cout << result + stack.size();
return 0;
}
/*
1 2 1 2 1 2 2 1 0 1 0 1
10
1 0
2 2
3 1
4 2
5 1
6 2
8 1
9 0
10 1
11 0
12 1
1
1 0
*/
[BOJ] 스카이라인 쉬운거
https://compy07.github.io/Blog/posts/boj/1863/