[백준 3015번 C/C++] 오아시스 재결합
[백준 3015번 C/C++] 오아시스 재결합

https://www.acmicpc.net/problem/3015
3015번: 오아시스 재결합
첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람
www.acmicpc.net
해결전략
자료 구조
스택 Stack
정답코드
#include <iostream> #include <stack> using namespace std; struct Info { int height, pair; // height: 키, pair: 조건을 만족하는 쌍의 수 }; int n; long long answer; // 계산할 조건을 만족하는 쌍의 수 stack<Info> st; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; int input; for (int i = 0; i < n; i++) { cin >> input; // 스택의 top에 있는 사람의 키가 현재 사람의 키보다 작은 동안 반복 while (!st.empty() && st.top().height < input) { answer += st.top().pair; // 조건을 만족하는 쌍의 수를 answer에 더함 st.pop(); // 스택에서 제거 } int sameHeight = 1; // 같은 키를 가진 사람의 수, 처음은 자기 자신만 있으므로 1로 시작 if (!st.empty()) { if (st.top().height == input) { // 바로 앞 사람과 새로 선 사람의 키가 같은 경우 answer += st.top().pair; // 조건을 만족하는 쌍의 수를 answer에 더함 sameHeight = st.top().pair + 1; // 같은 키를 가진 사람의 수 업데이트 if (st.size() > 1) answer++; // 스택에 사람이 2명 이상 있으면 answer 증가 st.pop(); // 스택에서 제거 } else if (st.top().height > input) { // 바로 앞 사람이 새로 선 사람보다 큰 경우 answer += 1; // 조건을 만족하는 쌍의 수를 1 증가 } } st.push({ input, sameHeight }); // 현재 사람의 정보를 스택에 저장 } cout << answer; return 0; }
문제에서 "앞 사람의 키가 같거나 작으면 서로 볼 수 있고, 같은 키를 가진 사람의 경우 추가적으로 처리해줘야 한다"라고 설명한다.
스택에 현재까지의 상태(=키(height)와 같은 키를 가진 사람의 수(pair))를 저장하여 사용한다.
주의!
answer의 값이 커질 수 있으므로 변수는 int가 아닌 long long을 사용해야 한다.
'⭐ 코딩테스트 > 백준' 카테고리의 다른 글
[백준 17136번 C/C++] 색종이 붙이기 (0) | 2024.03.26 |
---|---|
[백준 2623번 C/C++] 음악 프로그램 (0) | 2024.03.21 |
[백준 13907번 C/C++] 세금 (0) | 2024.03.14 |
[백준 13141번 C/C++] Ignition (0) | 2024.03.12 |
[백준 13977번 C/C++] 이항 계수와 쿼리 (0) | 2024.03.08 |
댓글
이 글 공유하기
다른 글
-
[백준 17136번 C/C++] 색종이 붙이기
[백준 17136번 C/C++] 색종이 붙이기
2024.03.26 -
[백준 2623번 C/C++] 음악 프로그램
[백준 2623번 C/C++] 음악 프로그램
2024.03.21 -
[백준 13907번 C/C++] 세금
[백준 13907번 C/C++] 세금
2024.03.14 -
[백준 13141번 C/C++] Ignition
[백준 13141번 C/C++] Ignition
2024.03.12
댓글을 사용할 수 없습니다.