[백준 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을 사용해야 한다.

 

---