반응형
https://www.acmicpc.net/problem/2493
2493번: 탑
첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1
www.acmicpc.net
[ 문제풀이 ]
1. stack<pair<int, int>> s를 만들어 타워의 인덱스와 높이를 저장합니다.
2. 타워의 높이를 입력받고, s.top()보다 타워의 높이가 더 크다면 (s.top() < h) s.pop()을 해줍니다. 왜냐하면 s.top()의 타워는 뒤의 타워가 더 크므로 더 이상 레이저를 수신할 수 없기 때문입니다.
3. s.top()보다 타워의 높이가 더 작다면 현재 s.top()의 인덱스를 출력합니다.
[ 소스코드 ]
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 | #include<iostream> #include<stack> using namespace std; int N; int main() { stack<pair<int,int>> s; scanf("%d", &N); for (int i = 1; i <= N; i++) { int h; scanf("%d", &h); while (!s.empty()) { if (s.top().second > h) { printf("%d ", s.top().first); break; } s.pop(); } if (s.empty()) { printf("0 "); } s.push({ i,h }); } } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 18436번 - 수열과 쿼리 37 (C++) (0) | 2023.01.14 |
|---|---|
| [ 백준 ] 14427번 - 수열과 쿼리 15 (C++) (0) | 2023.01.13 |
| [ 백준 ] 13975번 - 파일 합치기 3 (C++) (0) | 2023.01.11 |
| [ 백준 ] 16118번 - 달빛 여우 (C++) (0) | 2023.01.10 |
| [ 백준 ] 16562번 - 친구비 (C++) (0) | 2023.01.09 |