BOJ 33952 PPC와 CPP

문제 링크입니다.

문제 요약

P와 C로만 이루어진 문자열 $S$에서 PPC 또는 CPP를 삭제하는 연산을 반복해 빈 문자열로 만들 수 있는 지 판정하세요.

지울 수 있는 덩어리로 쪼개기

P의 개수가 C의 2배가 아니면 자명하게 불가능하므로 생각하지 않겠습니다.

문자열 $S$를 적당히 쪼개서 각각을 지워낼 수 있다면 전체 문자열 또한 지워낼 수 있습니다. 쉽게 지워낼 수 있는 문자열 조각의 조건을 찾아 봅시다.

첫 글자가 C인 길이 $3N$의 문자열을 가져옵니다. 이 문자열에는 C를 기준으로 분리되는 P 덩어리가 총 $N$구간 존재합니다. P가 총 $2N \ge N+1$개이므로 비둘기집 원리에 의해 이 중 P가 2개 이상 포함된 구간이 반드시 존재합니다. 이 구간을 첫 C가 아닌 인접한 C와 매칭해서 지워주면, 귀납적으로 한쪽 끝이 C이고 개수 조건을 만족하는 모든 문자열을 지울 수 있음을 알 수 있습니다.

지울 수 있는 덩어리로 못 쪼개기

위의 내용으로부터 각 부분문자열마다 개수 조건을 만족하고 C가 한쪽 끝에 있도록 문자열을 적당히 쪼갤 수 있으면 전체 문자열을 지울 수 있음을 확인할 수 있습니다. 다른 방법으로 쪼갤 수는 없을까요?

위의 방법으로 안 쪼개지는데 지울 수 있는 제일 짧은 문자열 $T$를 가져옵니다. 이 문자열의 양쪽 끝은 P이기 때문에(C이면 그 자체로 이미 조건에 맞게 쪼갠 꼴이 됩니다.), 마지막으로 지우게 되는 CPP 또는 PPC에 포함된 C를 기준으로 문자열을 둘로 쪼갤 수 있습니다.

일반성을 잃지 않고 마지막에 CPP를 지운다고 합시다. 앞쪽의 문자열은 자기들끼리 지워지고, 뒤쪽 문자열은 C가 첫 글자이므로 쪼개는 조건에 맞습니다. 앞쪽 문자열 역시 지울 수 있고 가장 짧은 쪼갤 수 없는 문자열 $T$보다 길이가 짧으므로 쪼갤 수 있는 문자열이게 됩니다.

따라서 위의 조건에 따라 문자열을 쪼갤 수 있음과 전체 문자열을 지울 수 있음이 필요충분조건입니다!

그리디하게 쪼갤 수 있으면 쪼개다가, 첫 문자가 C인 문자열이 나오는 순간 끊어주면 총 시간 복잡도 ${\cal O}(N)$에 구현할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int n; cin >> n;
	string s; cin >> s;
	int cnt = 0; for(auto& c : s){
		if(c == 'P') cnt++;
		else cnt -= 2;
	}
	if(cnt) return !(cout << "NO");
	bool ok = 1;
	for(auto& c : s){
		if(ok && c == 'C') return !(cout << "YES");
		ok = 0;
		if(c == 'P') cnt++; else cnt -= 2;
		if(!cnt && c == 'C') ok = 1;
	}
	if(ok) return !(cout << "YES");
	cout << "NO";
}