[백준/C++] 22354번 돌 가져가기

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

22354번: 돌 가져가기

내가 푼 문제중 제일 티어가 높은 문제이다.. 게다가 그리디라 생각하기가 엄청 어려웠다

우선 돌을 최적으로 가져가는 방법에 대해 설명하겠다.

1. 연속된 돌은 반드시 1개만 가져갈 수 있다 (= 연속된 돌에서는 점수를 2번 이상 얻을 수 없다)

-> 이 부분은 돌들을 그려놓고 한번 해보길 바란다. 이웃한 돌들이 색이 달라야 점수를 얻는데, 이웃한 돌이 같은 색이면 애초에 점수를 얻을 수 있는 환경이 아니다.

2. 그래서 퐁당퐁당 모양으로 바꿔준다

-> 돌들을 탐색하면서, 만약 같은 색의 돌을 만난다면 같은 색들 가진 돌 중 점수가 제일 큰 놈을 선택한다(그리디)

-> 같은 색의 돌이 2개 이상 있을 수 있다는 점을 유의하자. 시간복잡도는 O(n)이다. (배열을 한번만 돌기 때문)

3. 어떤 방식으로든 맨 끝( 맨 왼쪽과 맨 오른쪽) 은 가져가도 점수를 얻지못한다!

-> 그렇기 떄문에, 양 끝 값을 0으로 바꿔주고 내림차순으로 정렬해주자.

4. 그런 다음, 내림차순으로 정렬된 배열에서 (v.size -2) / 2 를 올림한 값만큼 정답에 더해주면 된다.

-> -2를 하는 이유? 양 끝을 제외시키기 때문

-> 왜 (v.size()-2) /2 만큼만 선택?

= BWBWBWB라고 하자. 첫번째 B를 고르면 BWWBWB 가 되고 가운데 B를 고르면 BWWWB가 된다. 이때 값을 더 가지기 위해선 겹치는 W 중 작은 놈 둘을 버려야한다. 그러면, BWB가 되고, 이제 W를 골라서 총 3개를 고를 수 있다. (양 끝은 고려 x !!!!)

첫번째 B가 아니라 가운데 W를 고른다고 해보자. 그럼 BWBBWB가 되고 첫번째 W를 선택할 수 있다. 그러면 남은건 BBBWB가 되므로 마지막 W를 고를 수 있고, 이 역시 마찬가지로 최대 3개를 고를 수 있다

이를 수식으로 표현하면 (7-2) / 2 를 올림한 값과 동일하다.

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;

ll n,ans=0;
string s;
vector<ll> score;
vector<ll> v;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> s;

    for(ll i=0; i<n;i++){
        ll num;
        cin>> num;
        score.push_back(num);
    }

    ll cmp;
    for(ll i=0; i<n;i++){
        cmp = score[i];
        if(s[i]==s[i+1]) {
            cmp = max(cmp, score[i + 1]);
            ll j=i+1;
            for ( ; j < n; j++) {
                if (s[j] == s[j + 1])
                    cmp = max(cmp, score[j+1]);
                else break;
            }
            i = j;
        }
        v.push_back(cmp);
    }
    //for(auto k :v) cout << k;
    v[0] = 0;
    v[v.size()-1]=0;
    sort(v.begin(),v.end(),greater<>());
    //for(auto k :v) cout << k;

    ll siz;

    if(v.size() < 3){
        cout << 0; return 0;
    }
    else{
        siz = (v.size()-3) / 2 + 1;
    }
    for(ll i=0; i<siz;i++){
        ans += v[i];
    }
    cout << ans;
    return 0;
}