백준 22354번 돌 가져가기

🔒문제 url

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

🔑알고리즘

아래와같은 경우를 생각해보자.양 끝에 있는 돌로는 점수를 얻을 수 없으므로, 두 개의 $W$ 중 더 높은 점수의 돌이 최대 점수가 됨을 알 수 있다.
즉, 연속된 색의 돌이 있다면 그 중 최대 점수의 돌만큼 점수를 획득한다.
하나의 예시를 더 살펴보자.
위의 경우 점수의 후보가 될 연속된 구간은 다음과같다.
1. W, 10 W, 20 W, 30
2. B, 40 B, 50
3. W, 60
연속된 색의 구간에서 점수를 얻을 수 있는 돌은 하나이므로,
어떤 순서로 놓여있든 아래와같이 두 색이 번갈아 나타나는 순서로 나타낼 수 있다. 이때 연속된 구간에서의 최대값을 택해야함에 유의하자.
이제 돌을 하나씩 가져가 점수를 획득해보자.
하나의 돌을 선택하면, 양 옆에 있던 같은 색의 돌이 붙어있게되므로 반드시 하나의 돌을 포기하게 된다.
즉, 점수를 얻을 수 있는 돌의 후보 수가 $k$라면, [($k$+1)/2] 개의 돌로부터 점수를 얻을 수 있다. 위에 경우에서는 $k$=3이므로 2개의 돌로부터 점수를 얻을 수 있게되어 110이 최대 점수가 된다.

---

1. 연속된 구간에서의 최대값을 모아 내림차순 정렬한다.
2. 정렬된 값의 수가 $k$라면, 앞에서부터 [($k$+1)/2] 개의 원소의 합을 출력한다.

🐾부분 코드

priority_queue<ll> score;
for (int i = 1; i <= n - 2; i++)
{
    priority_queue<ll> pq;
    bool candidate = false;
    char now = str[i];
    if (str[i-1] != now)
    {
        int idx = i;
        while(idx != n)
        {
            if(str[idx] != now)
            {
                candidate = true;
                i = idx-1;
                break;
            }
            pq.push(A[idx++]);
        }
    }
    if(candidate) score.push(pq.top());
}

<연속 구간 최대값 정렬>
priority_queue를 사용하여 연속된 구간에서의 값들pq 중 최대값을 score에 push한다.
연속된 구간은 구간의 양 옆에 구간 내 돌의 색과 다른 색의 돌이 위치해야함을 이용하여 탐색한다.

ll ans = 0;
int cnt = score.size();
for (int i = 0; i < (cnt+1)/2; i++) ans += score.top(), score.pop();
cout << ans;

<($k$+1)/2개의 돌만큼 점수 획득>
연속된 구간에서의 최대값을 모두 찾았다면, 큰 순서대로 ($k$+1)/2개의 돌을 선택하여 점수를 더한 후 출력한다.

🪄전체 코드

#include <iostream>
#include <queue>
#include <string>

using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

typedef long long ll;
int n;
string str;
ll A[300001];

void INPUT()
{
    IAMFAST
    cin >> n >> str;
    for (int i = 0; i < n; i++) cin >> A[i];
}

void SOLVE()
{
    priority_queue<ll> score;
    for (int i = 1; i <= n - 2; i++)
    {
        priority_queue<ll> pq;
        bool candidate = false;
        char now = str[i];
        if (str[i-1] != now)
        {
            int idx = i;
            while(idx != n)
            {
                if(str[idx] != now)
                {
                    candidate = true;
                    i = idx-1;
                    break;
                }
                pq.push(A[idx++]);
            }
        }
        if(candidate) score.push(pq.top());
    }

    ll ans = 0;
    int cnt = score.size();
    for (int i = 0; i < (cnt+1)/2; i++) ans += score.top(), score.pop();
    cout << ans;
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

게임 이론일줄 알았지... 어려워봤자 돌 게임 7 정도일 줄 알았지....
너덕분에 새벽 6시 30분에 잤다가(심지어 못 풀고) 일어나서 다시 피눈물 흘리면서 풀었다.. 정말 힘들었어.. 오늘 공부는 다했다..
그래도 골드 6문제 풀어도 rating 1점 오르던거 덕분에 7점 올랐다. 도대체 얼마만이냐.