[C++] 22354번 돌 가져가기 - 그리디, 정렬

22354번 돌 가져가기

 

1. 문제

• N개의 돌이 일렬로 나열되어 있다. 각 돌은 흰색 또는 검은색의 색상을 갖는다.
• 돌들을 왼쪽부터 1~N번 돌이라고 하자. i번째 돌의 무게는 \(A_i\)이다.
• 당신은 나열된 돌들 중 하나를 골라 가져가는 것을 모든 돌이 없어질 때까지 N번 반복하려고 한다.
• 돌을 가져갈 때, 만약 그 돌이 현재 나열된 돌 중 가장 왼쪽이나 가장 오른쪽이 아니며, 가져간 돌에 인접한 두 돌 모두 가져간 돌과 다른 색인 경우 당신은 가져간 돌의 무게만큼의 점수를 얻는다.
• 가장 많은 점수를 얻을 수 있도록 돌을 가져가는 방법을 구하여라.

<입력>

• -1- 양의 정수 \(N(1 \leq N \leq 3 \times 10^5)\)
• -1- B또는 W로만 이루어진 길이 N의 문자열 S가 주어진다.
  • S의 i번째 문자 \(S_i\)는 왼쪽에서 i번째 돌의 색을 나타낸다. B는 돌이 검은색임을, W는 돌이 흰색임을 뜻한다.
• -1- N개의 정수 \(A_1 ,A_2, ..., A_N\)이 주어진다. \((1 \leq A_i \leq 10^9)\)

<출력>

• 최적의 방법으로 돌을 가져갔을 때 얻을 수 있는 점수를 출력한다.

 

2. 재정의

• X

 

3. 해결 방법

• W묶음과 B묶음 각각에서 결국 하나의 점수만 얻을 수 있음을 알 수 있다. 이 때 만약 묶음 개수가 N개가 나왔다면 (N-1)/2개 만큼 점수를 얻을 기회가 생긴다는 것을 알 수 있고 이중에서 최대 점수만 얻으면 된다.

 

4. 실수한 점, 개선할 점

• 앞으로 노트에 꼭 써보고 하자.

 

<코드>

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

typedef long long int lld;

const int INF = 1000000001;
const int MAX_N = 300001;

int N;
string color;
int A[MAX_N];
vector<int> num;

void input() {
    cin >> N;
    cin >> color;
    
    for(int i=0; i<N; i++)
        cin >> A[i];
}

void solve() {
    int M = 0;
    for(int i=1; color[i]; i++) {
        if(color[i] != color[i-1]) {
            num.push_back(M);
            M = 0;
        }
        M = max(M, A[i]);
    }
    
    sort(num.begin(), num.end());
    lld res = 0;
    
    for(int i=0; i<(int)num.size()/2; i++)
        res += num[(int)num.size()-1-i];
    
    cout << res;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    solve();
    
    return 0;
}

 

 

<문제 바로가기>

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

22354번: 돌 가져가기