[C/C++] 백준 31778번 - PPC 만들기

✏️ 문제 링크

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

 

 

✏️ 문제 설명

 

 

✏️ 문제 풀이

얼마 전 포스텍 open contest에 나왔던 문제입니다.

군대에서 짜투리 시간 내서 참가해서 도전했었던 문제인데 계속 풀지를 못했던 문제입니다..

분명 딱 봤을 때 투포인터랑 dp를 이용해야 한다는 거는 알았는데 11번 제출해서 모두 틀렸습니다 하하하

 

거두절미하고 문제 본론으로 넘어가보겠습니다.

문자열을 교환하고 PPC 문자열을 만들 수 있는 개수를 출력해야 하는데, 교환은 최대 k번할 수 있습니다.

이 말은 꼭 k번을 교환할 필요는 없다는 말입니다. 문자열 교환의 핵심은 P가 최대한 앞으로 C가 최대한 뒤로 가야 합니다.

여기서 투 포인터 방식을 이용해서 교환을 해야 합니다. 자세한 내용은 코드를 보시면 될 것 같습니다.

 

그다음은 PPC문자열의 개수를 세어야 하는 부분입니다.

Pcount배열에 각 인덱스당 P가 몇 개 있는지 저장해 줍니다. 그런 다음 Ccount배열에 각 인덱스당 C가 몇 개 있는지 세줘야 하는데 C는 문자열의 뒤쪽에 포진하는 경우가 대부분이므로 개수를 맨 뒤에서부터 앞쪽으로 세줘야 합니다.

이렇게 두 개의 배열을 업데이트 해준 후 PPC의 개수를 세줍니다. PPC의 개수는 for문을 돌리면서 P를 만나면 ans에

앞의 P의 개수 * 뒤의 C의 개수의 값을 더해줍니다.

 

 

✏️ 문제 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long

long long Pcount[200001]; // 얘는 그냥 P의 개수
long long Ccount[20000];

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	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 left = 0, right = N + 1;

	while (left < right && K) {
		while (left < N && s[left] != 'C')
			left++;
		while (right >= 0 && s[right] != 'P')
			right--;
		if (left >= right)
			break;
		K--;
		swap(s[left], s[right]);
	}

	for (int i = 1; i <= N; i++) {
		if (s[i] == 'P')
			Pcount[i] = Pcount[i - 1] + 1;
		else
			Pcount[i] = Pcount[i - 1];
	}

	for (int i = N; i >= 1; i--) {
		if (s[i] == 'C')
			Ccount[i] = Ccount[i + 1] + 1;
		else
			Ccount[i] = Ccount[i + 1];
	}

	ll ans = 0;
	for (int i = 1; i <= N; i++) {
		if (s[i] == 'P') {
			ans += Pcount[i - 1] * Ccount[i];
		}
	}
	cout << ans;
}