백준 31778 PPC 만들기

https://boj.ma/31778/t 

31778번: PPC 만들기

 

 

P와 C로만 이루어진 배열에서 위치변경 행위를 최대 K번 수행해서 부분문자열중 PPC 의 갯수를 최대화 하는 문제입니다.

PPC 부분 문자열의 정의가 "1≤𝑖<𝑗<𝑘≤𝑁 이고, 𝑆𝑖=𝑆𝑗= P, 𝑆𝑘= C인 (𝑖,𝑗,𝑘)의 개수"이기 때문에

P는 최대한 앞으로 C는 최대한 뒤로 옮겨줘 PPPPPP.....CCCCCC 형태가 되어야 PPC 부분문자열의 갯수를 최대화 할 수 있습니다.

그리디하게 위와 같은 형태로 만들었다고 쳐도, PPC 부분 문자열을 세어주는 과정이 남았습니다.

저는 PPC중 가운데 있는 P에 집중했습니다.

 

P를 만날때 마다 (내 앞의 P 갯수) * (내 뒤에 C갯수) 를 정답에 누적해주면 될것 같습니다.

하지만 이걸 모든 P를 만날때마다 하나하나 구해준다면 O(N^2)으로 시간초과입니다.

 

내 앞에 몇개 있는지, 내 뒤에 몇개 있는지 구하는것은 누적합을 통해 최적화가 가능합니다.

 

prefix_p, suffix_c 배열을  통해 O(N)에 전처리하고 P를 만날 때 마다

prefix_p[i - 1] * suffix_c[i] 를 정답에 누적해주면 전체 시간복잡도 O(N)으로 해결 가능합니다.

 

코드(c++)

#include <bits/stdc++.h>

#define endl "\n"
#define NM 100101
#define MAX 1010100
#define BIAS 1048576
#define MOD 1000000007
#define X first
#define Y second
#define INF 1000000000
#define FOR(i) for(int _=0;_<(i);_++)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
using namespace std;


int main() {
    fastio
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int n, k;
    cin >> n >> k ;
    vector<char> s(n + 2);
    s[0] = s[n + 1] = 'X';
    for (int i = 1 ; i <= n; i++) cin >> s[i];
    int l = 0, r = n + 1;
    while (l < r && k){ // P는 최대한 앞으로 두고 C는 최대한 뒤로 두기
        while (l < n && s[l] != 'C') l++;
        while (r >= 0 && s[r] != 'P') r--;
        if (l >= r) break;
        k--;
        swap(s[l], s[r]);
    }
    // 누적합
    vector<ll> prefix_p(n + 1), suffix_c(n + 2);
    for (int i = 1; i <= n; i++){
        prefix_p[i] = prefix_p[i - 1] + (s[i] == 'P');
    }
    for (int i = n; i >= 1; i--){
        suffix_c[i] = suffix_c[i + 1] + (s[i] == 'C');
    }

    ll ans = 0;
    for (int i = 1; i <= n; i++){
        if (s[i] == 'P'){ // P를 만날 때마다
            ans += prefix_p[i - 1] * suffix_c[i]; // 내 앞에 P 갯수 * 내 뒤에 C갯수
        }
    }
    cout << ans << endl;
    return 0;
}

 

 

 

 

인덱스 실수로 고생좀 했습니다.

그리고 prefix_p 배열을 굳이 만들지 말고 문자열을 순회하며 P의 갯수를 따로 누적해주는 것만으로도 해결할 수 있습니다.