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

 

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

 

https://www.acmicpc.net/problem/3015

3015번: 오아시스 재결합

---

 

해결전략

 

자료 구조
스택 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을 사용해야 한다.

 

---