[코드포스 Practice22] C. Alice, Bob, Two Teams

 

구해야 하는 값이 연속적으로 있어서 구간합이나 투포인터가 떠오르긴 했는데 구간합은 시작과 끝을 정하는 부분이 많아서 패스하고 투포인터는 l, r이 움직이는 기준을 잡기 어려워서 포기했다. 시간 촉박한 와중에 투포인터 ppt도 봤는데 거기서도 투포인터는 주로 구간의 길이를 구한다고 했고 최댓값을 구하는 데 적합하지 않아서 패스했음.

 

이 문제도 내가 잘못 이해했다. 여기서 prefix랑 suffix란 용어가 나왔는데 이걸 찾아보니 접두사 접미사였다. 그래서 구간을 선택하면 그 구간의 처음과 끝을 바꾸는 건가 싶었는데 예시를 보니 아니었다. 도저히 어떤 값인지 알 수 없어서 패스하고 풀기 시작했는데 알고보니 prefix가 문자열의 처음부터 특정 위치까지의 문자열을 뜻하는 것 같았다. suffix는 반대로 특정 위치에서 맨 끝까지의 문자열이고. 

 

그럼 부분합 쓸 수 있겠다! 미리 점수 합 구한 다음 최댓값은 처음부터 끝까지 훑으면서 찾으면 되겠음. 아 뭐야 생각외로 간단하잖아.

 

 

 

 

그래서 점수의 변화량을 담는 배열을 만들어두고 그 변화량 중 가장 큰 값을 저장한다. 가장 큰 변화량과 기존의 값을 더한 값과 기존의 값 두 개를 비교해서 (변하지 않았을 때 값이 더 클 수 있으므로) 큰 값을 출력하면 된다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
#define MAX 1e9
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
 
int main() {
    int n;
    scanf("%d", &n);
    
    vector<i64> v(n);
    for (int i = 0; i < n; i++)
        scanf("%lld", &v[i]);
        
    string s;
    cin >> s;
    
    i64 sum_b = 0;
    vector<i64> point(n);
    for (int i = 0; i < n; i++)
    {
        if (s[i] == 'B')
        {
            sum_b += v[i];
            point[i] = v[i] * -1;
        }
        else
            point[i] = v[i];
    }
    
    vector<i64> left(n);
    left[0] = point[0];
    for (int i = 1; i < n; i++)
        left[i] = point[i] + left[i-1];
     
    vector<i64> right(n);
    right[n-1] = point[n-1];
    for (int i = n-2; i >= 0; i--)
        right[i] = point[i] + right[i+1];
    
    i64 max1 = *max_element(left.begin(), left.end());
    i64 max2 = *max_element(right.begin(), right.end());
    
    cout << max(max(max1, max2) + sum_b, sum_b);
    
    return 0;
}

 

배열 안 만들고 구할 수도 있었을 것 같은데 그냥 배열 만들었다. 편하게 갑시다.. 

 

 

---

 

 

나는 값의 변화량을 저장했는데 a, b값을 따로 저장했다. 뒤집는 걸 a 점수의 합이라 생각할 수 있구나. 신기하다.

 

 

int main() {
    int n;
    scanf("%d", &n);
    
    vector<i64> a(n+1);
    vector<i64> b(n+1);

    vector<int> p(n+1);
    for(int i = 1; i <= n; i++)
        scanf("%d", &p[i]);

    string s;
    cin >> s;
    for (int i = 0; i < n; i++)
    {
        a[i+1] = a[i];
        b[i+1] = b[i];

        if (s[i] == 'A')
            a[i+1] += p[i+1];
        else
            b[i+1] += p[i+1];
    }

    i64 ans = b[n];

    for (int i = 1; i <= n; i++)
        ans = max({ans, a[i] + b[n] - b[i], b[i] + a[n] - a[i]});
    
    printf("%lld\n", ans);
    return 0;
}