BOJ 3015 오아시스 재결합 해설

작성일 | In

문제 링크

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

해설

개인적으로 이 문제를 해결하는 과정에서 어려움을 겪었습니다.

아무리 생각해도 문제를 해결하기 위한 감도 잡히지 않아 인터넷 해설을 참고하여 해결한 문제입니다.

알고리즘 분류

그리디 스타일의 스택 활용 문제로, 스택을 활용하여 최적화를 해야 합니다.

문제 해결

만약 A라는 사람의 키가 B라는 앞 사람의 키보다 크다면, A뒤에 있는 사람들은 B를 볼 수 없게 됩니다.

다른 말로, A 사람이 마지막으로 B 사람을 볼 수 있는 것입니다.

이 특성을 활용하여, 앞 사람의 키가 현재 탐색하고 있는 사람의 키보다 작다면 앞 사람을 지울 수 있습니다.

또, 만약 A와 B가 서로를 볼 수 있다면, A와 키가 같은 모든 사람을 볼 수 있습니다.

이를 활용하여 연속되어 있는 같은 키의 갯수를 새주어, 효과적으로 표현하는 것입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
#define ll long long int

int main(void) {
    ll n;
    cin >> n;
    ll ans = 0;
    stack<pair<ll, ll>> s;
    while (n--) {
        ll x, cnt = 1;
        cin >> x;
        while (!s.empty() && x >= s.top().first) {
            ans += s.top().second;
            if (s.top().first == x) cnt = s.top().second + 1;
            s.pop();
        }
        if (!s.empty()) ans++;
        s.push({x, cnt});
    }
}