[백준] BOJ 22354 돌 가져가기

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

 

 

| Solved.ac 난이도 : P2 |

 

문제 추천도 : 9/10

 

 

🏷️ 그리디

 

 

풀이

 

1. 인접하며 같은 색을 가지는 돌들은 그중 1개 또는 0개만 선택할 수 있습니다.

• 어떤 돌을 선택하려면, 그 돌의 양 옆이 다른 색의 돌이어야하기 때문입니다.

2. 1에 의해서 같은 색의 인접한 돌들을 무게가 가장 큰 돌 하나로 치환할 수 있습니다.

• 여기까지 진행하면 돌들의 상태는 $WBWBWB...$이나 $BWBWBW...$가 됩니다.

3. 또한, 맨 앞과 맨 끝 돌은 선택할 수 없습니다.

 

4. ⭐ KeyPoint : 다른 색의 돌이 교차하는 상태에서는 n개의 돌 중 색깔에 상관없이 최대 $\lceil(n-2)/2\rceil$개의 돌을 반드시 선택할 수 있습니다. $(n-2$는 n개의 돌 중 양 맨 끝 두 개의 돌을 뺀 것입니다) - 아래에서 증명합니다.

• 여기서 $n$은 인접한 돌들을 합친 상태, 다른 색의 돌들이 교차하는 상태에서의 돌의 개수입니다.

 

5. 따라서 정리하면, 먼저 인접한 같은 색의 돌들을 그들의 최대 무게 돌 하나로 바꾸고, 맨 앞과 맨 끝 돌을 제외한 돌들 중가장 큰 돌 $\lceil(n-2)/2\rceil$개의 무게를 합한 것이 답이 됩니다. 

 

---

 

 

 ⭐ KeyPoint : 다른 색의 돌이 교차하는 상태에서는 n개의 돌 중 색깔에 상관없이 최대 $\lceil(n-2)/2\rceil$개의 돌을 반드시 선택할 수 있습니다. - 에 대한 증명

(ucpc 2021 예선 공식 에디토리얼을 풀어서 설명한 것입니다. 공식 에디토리얼은 여기에서 볼 수 있습니다.)

 

 

기저사례)

$n=1, 2$ -> 모두 양 끝 점에 속하므로 어떤 돌도 선택할 수 없습니다.

$n=3$ -> 양 끝 점을 제외하면 1개의 돌이 남으며, 이 돌을 고를 수 있습니다.

 

 

이제 귀납적으로 해결해봅시다.

먼저, $f(n, k)$를 $n$개의 돌 중 정답이 되는 돌의 개수가 $k$개인 상태라고 정의합니다.

 

$n ≥ 4$일 때, 처음 상태는 $f(n-2, \lceil(n-2)/2\rceil)$입니다.

또한, 정답에 포함되어야 하는 돌 $\lceil(n-2)/2\rceil$를 제외하면 정답이 아닌 돌이 한 개 이상 존재합니다.

 

정답에 포함되는 돌들 중 한 쪽에 양 끝 돌이 아니며, 정답에 포함되지 않는 돌이 있는 돌 하나를 $x$라고 합시다.

그리고, $x$옆에 양 끝 돌이 아니며, 정답에 포함되지 않는 돌을 $y$라고 합시다. 이때, $x$와 $y$는 서로 다른 색을 가집니다.

 

그렇다면, $y$를 가져간 다음, $x$를 가져갈 수 있으므로, 이를 시행합니다. -> 총 돌의 개수는 2개 줄고, 정답인 돌의 개수는 1개가 줄어듭니다.

이는 $f(n, \lceil(n-2)/2\rceil)$ -> $f(n-2, \lceil(n-2)/2\rceil-1)$로 표현할 수 있습니다.

 

돌의 개수가 $n-2$일 때, 정답인 돌의 개수는 $\lceil(n-4)/2\rceil$이며 올림 연산은 1을 꺼내도 결과가 같기에 $\lceil(n-4)/2\rceil=\lceil(n-2)/2\rceil-1$이 됩니다.

이는 위에서 $x$와 $y$를 빼는 시행을 한 후의 정답인 돌의 개수인 식과 같기에 색이 다른 돌 $y$와 $x$를 제거하는 시행을 한 후, 총 돌의 개수가 $n-2$개인 답을 구하는 것과 동일해집니다.

따라서 이를 귀납적으로 반복하면 답과 동일해집니다.

 

---

 

 

구현
라이트모드로 보셔야 잘 보입니다

풀이를 이해하셨다면 구현은 직접 자신의 결로 써보시길 추천드립니다.

# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define fastio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
int n;
string s;
priority_queue<ll> pq;
ll arr[300010];
int main()
{
    fastio;
    cin>>n>>s;
    ll mx=0;
    int flag=0;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
        if(i==0) continue;
        if(flag && s[i]!=s[i-1])
        {
            pq.push(mx);
            mx=0;
        }
        if(!flag && s[i]!=s[i-1])
        {
            mx=0;
            flag=1;
        }           
        mx=max(mx,arr[i]);
    }
    ll res=0;
    n=pq.size();
    for(int i=1;i<=(n+1)/2;i++)
    {
        res+=pq.top();
        pq.pop();
    }
    cout<<res;
}