[22354] 돌 가져가기

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

22354번: 돌 가져가기

<문제>

UCPC에 나온 문제라 증명까지 풀이 슬라이드에 잘 나와있다. (https://ucpc.me/assets/ucpc21-prelim-solutions.pdf)

동일한 색의 돌이 연속으로 있을 때에는, 그중 하나만 가져갈 수 있다는 것이 풀이를 떠올리기 위한 핵심이 된다.

연속한 것 중 하나만 가져갈 수 있다면 모든 경우는 WBWB...나 BWBW..처럼 번갈아 나오는 경우로 압축할 수 있는데, 

양끝은 어처피 못 가져가니 이를 제외한, ceil((n-2)/2)개를 큰 것부터 선택해주면 된다.

 

구현을 하다 살짝 말려들어버린 부분이 있는데, 예상컨데 문자열의 마지막 부분이 빠지거나,

들어가면 안되는 가장 끝이 큐에 들어가 버리는 문제가 발생했던 거 같다.

<소스코드>

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, ans, a[300001];
string s;
vector<pair<char, int>> v, base;
priority_queue<ll> q;
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> s;
    ll i;
    for (i = 0; i < n; i++) cin >> a[i];
    for (i = 0; i < n; i++) v.push_back({s[i], a[i]});
    base.push_back({v[0].first, v[0].second});
    for (i = 1; i < n; i++) {
        auto cur = base.back();
        auto nxt = v[i];
        if (cur.first == nxt.first && cur.second < nxt.second) {
            int idx = base.size() - 1;
            base[idx] = nxt;
        } else if (cur.first != nxt.first) {
            base.push_back(nxt);
        }
    }
    ll nn = base.size();
    ll sz = ceil((double)(nn - 2) / (double)2);
    for (i = 1; i < nn - 1; i++) {
        // cout << "push: " << base[i].second << "\n";
        q.push(base[i].second);
    }
    while (sz--) {
        ans += q.top();
        q.pop();
    }
    cout << ans;
    return 0;
}