반응형
https://www.acmicpc.net/problem/6198
6198번: 옥상 정원 꾸미기
문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으
www.acmicpc.net
[ 문제풀이 ]
1. stack이 비어있지 않고, 건물의 높이 h의 값이 stack.top보다 크거나 같을 경우 st.pop을 해주고, st이 완전히 비기 전까지 반복해줍니다.
2. cnt에 현재 st의 size를 더해줍니다. 이때, cnt의 최댓값이 약 32억이므로 자료형을 long long으로 선언해줍니다.
3. stack에 건물의 높이 h를 push합니다.
4. cnt를 출력합니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | #include<iostream> #include<stack> #define ll long long using namespace std; int N; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N; stack<int> st; ll cnt = 0; for (int i = 0; i < N; i++) { int h; cin >> h; if (i == 0) { st.push(h); } else { while (st.top() <= h) { st.pop(); if (st.empty()) break; } cnt += st.size(); st.push(h); } } cout << cnt; } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 5430번 - AC (C++) (0) | 2023.07.09 |
|---|---|
| [ 백준 ] 17298번 - 오큰수 (C++) (0) | 2023.07.08 |
| [ 백준 ] 1456번 - 거의 소수 (C++) (0) | 2023.07.06 |
| [ 백준 ] 1038번 - 감소하는 수 (C++) (0) | 2023.07.05 |
| [ 백준 ] 11402번 - 이항 계수 4 (C++) (0) | 2023.07.04 |