백준 31778: PPC 만들기
https://www.acmicpc.net/problem/31778
포닉스에게는 아끼던 문자열 S가 있다. S는 길이가 N이며 알파벳 대문자 C와 P만으로 이루어져 있는 문자열이다. 문자열 S의 i번째 문자는 S_i이 나타낸다.
포닉스는 PPC에 참가하는 팀들을 위해 문자열 S 대회장을 장식하려 한다. 포닉스는 대회 전, S에 다음과 같은 연산을 최대 K번 시행할 수 있다.
1≤i<j≤N인 두 정수 i, j를 골라 S_i와 S_j를 바꾼다.
포닉스의 목표는 완성된 문자열 S에 PPC 부분문자열이 가장 많게 하는 것이다. PPC 부분문자열의 개수란, 1≤i<j<k≤N이고 S_i=S_j=' P', S_k=' C'인 (i,j,k)의 개수를 의미한다.
포닉스가 만들 수 있는 PPC 부분문자열의 개수의 최댓값을 구하여라.
문제는 두 단계로 나눌 수 있다.
1단계는 PPC 부분문자열의 개수가 최대가 되도록 연산을 K번 수행해 문자열 S를 완성시키는 것이다.
2단계는 완성된 문자열 S에서 PPC 부분문자열의 개수를 구하는 것이다.
1단계를 푸는 것은 그리디 방식이다. P를 최대한 왼쪽으로 밀어넣고 C를 최대한 오른쪽으로 밀어넣어야 하기 때문이다. 방법은 투 포인터 방식을 이용할 것이다.
문자열의 양쪽 끝에서 시작하여, 왼쪽에 있는 C와 오른쪽에 있는 P를 만난 때마다 둘의 위치를 바꾸는 연산을 해줄 것이다.
두 개의 포인터 l (0에서 시작) 그리고 r (N-1에서 시작)을 이용해준다.
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
int main()
{
ll n;
cin>>n;
ll k;
cin>>k;
string a;
cin>>a;
ll l=0,r=n-1;l은 점점 커지고, r은 점점 작아질 것이다.
예시 중 하나인 CCPCPPCP를 이용해 설명하겠다. K는 2이다.
| 인덱스 | 0 = l | 1 | 2 | 3 | 4 | 5 | 6 | 7 = r |
| 값 | C | C | P | C | P | P | C | P |
l이 0이고 r이 7에서 시작한다.
S[l]이 C고 S[r]이 P이다. 따라서 둘의 위치를 바꿔준다. 그 후 l을 1 증가시키고 r을 1 감소시킨다.
| 인덱스 | 0 | 1 = l | 2 | 3 | 4 | 5 | 6 = r | 7 |
| 값 | P | C | P | C | P | P | C | C |
이번엔 r이 C이다. 오른쪽 끝에 C가 있는 경우는 바꾸면 손해다. C가 오른쪽에 있을수록 좋기 때문이다. 그러므로 S[6]은 위치를 바꿀 필요 없다. r을 1 감소시킨다.
| 인덱스 | 0 | 1 = l | 2 | 3 | 4 | 5 = r | 6 = r | 7 |
| 값 | P | C | P | C | P | P | C | C |
S[l]이 C고 S[r]이 P이다. 따라서 둘의 위치를 바꿔준다. 그 후 l을 1 증가시키고 r을 1 감소시킨다.
| 인덱스 | 0 | 1 | 2 = l | 3 | 4 = r | 5 | 6 = r | 7 |
| 값 | P | P | P | C | P | C | C | C |
K가 2인데, 연산을 두 번 했으니 더 이상의 연산은 할 수 없다. 연산을 종료한다.
while(k>0&&r>l)//연산을 k번 수행했거나, l이 r보다 크거나 같아지면 연산을 종료한다.
{
if(a[l]=='P')
{
l++;
continue;
}
if(a[r]=='C')
{
r--;
continue;
}
//a[l]이 C이고 a[r]이 P인 경우에만 아래의 코드들을 실행할 수 있다.
//아니라면 위 조건문들에 걸려 continue; 코드에 의해 아래의 코드를 스킵하기 때문이다.
a[l]='P';
a[r]='C';
l++;
r--;
k--;
}
이제 다음, 2단계로 넘어간다. PPC 부분문자열을 세는 것이다. 방법은 세 가지를 생각해볼 수 있다.
1. C를 기준으로 세기
2. 첫 번째 P를 기준으로 세기
3. 두 번째 P를 기준으로 세기
1번 방법으로 예를 들자면 문자열 S에서 모든 C에 대해 그 C 앞에 등장하는 P의 개수를 세는 것이다. 그 중 2개를 순서 없이 선택하는 경우의 수(조합)을 얻어서 모두 더하면 된다.
아까 얻은 문자열
PPPCPCCC 로 예를 들면
C 앞에 등장하는 P의 개수는 3개다. 그 중 2개를 뽑는 조합은 3C2, 즉 3이다. 이것이 바로 C를 포함하는 PPC 부분문자열의 개수다.
C 앞에 등장하는 P의 개수는 4개다. 그 중 2개를 뽑는 조합은 4C2, 즉 6이다. 이것이 바로 C를 포함하는 PPC 부분문자열의 개수다.
C 앞에 등장하는 P의 개수는 4개다. 그 중 2개를 뽑는 조합은 4C2, 즉 6이다. 이것이 바로 C를 포함하는 PPC 부분문자열의 개수다.
C 앞에 등장하는 P의 개수는 4개다. 그 중 2개를 뽑는 조합은 4C2, 즉 6이다. 이것이 바로 C 를 포함하는 PPC 부분문자열의 개수다.
모두 합하면 3+6+6+6=21이다.
이 때 모든 C마다 일일히 센다면 시간복잡도가 너무 커진다. 따라서 특정 위치 앞에 등장하는 P의 개수를 누적 합 배열에 저장시켜두면 좋을 것이다.
2번 방법은 조금 복잡하다. 왜냐하면 기준을 첫 번째 P로 잡는다면 그 뒤에 나오는 P와 C는 P가 C보다 먼저 나와야 한다는 조건이 있어, 그 개수를 계산하기 까다롭다. 그래서 1번 방법처럼 단순히 첫 번째 P 다음에 나오는 P의 개수와 C의 개수만 안다고 해서 풀 수 없다. 그래서 3번 방법을 이용할 것이다.
두 번째 P의 위치를 기준으로 세는 것이다. 어떤 P를 기준으로 그 앞에 등장하는 P의 개수와 그 뒤에 등장하는 C의 개수의 곱은 그 P를 두 번째 P로 삼는 PPC 부분문자열의 개수다.
PPPCPCCC 로 예를 들면
P 앞에 등장하는 P의 개수는 0이고 뒤에 등장하는 C의 개수는 4이다. 그 곱은 0이다.
P 앞에 등장하는 P의 개수는 1이고 뒤에 등장하는 C의 개수는 4이다. 그 곱은 4이다.
P 앞에 등장하는 P의 개수는 2이고 뒤에 등장하는 C의 개수는 4이다. 그 곱은 8이다.
P 앞에 등장하는 P의 개수는 3이고 뒤에 등장하는 C의 개수는 3이다. 그 곱은 9이다.
모두 합하면 0+4+8+9=21이다.
나는 3번 방법으로 풀었고, 구현 방법은 다음과 같다.
ll p=0,c=0;
for(ll i=0;i<n;i++)
{
if(a[i]=='C')
{
c++;
}
}//c는 문자열 속 C의 개수가 된다.
ll ans=0;
for(ll i=0;i<n;i++)
{
if(a[i]=='P')
{
ans+=p*c;
p++;//P를 만날 때마다 p에 1을 더해준다.
}
else
{
c--;//C를 만날 때마다 c에 1을 빼준다.
}
}
cout<<ans;
return 0;
}
p라는 변수에 i번째 위치 앞에 등장하는 P의 개수를, c라는 변수에 i번째 위치 뒤엥 등장하는 C의 개수를 저장했고, 모든 P마다 p*c값을 계산해 답에 더해주었다.
전체 소스코드는 다음과 같다.
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
int main()
{
ll n;
cin>>n;
ll k;
cin>>k;
string a;
cin>>a;
ll l=0,r=n-1;
ll p=0,c=0;
while(k>0&&r>l)
{
if(a[l]=='P')
{
l++;
continue;
}
if(a[r]=='C')
{
r--;
continue;
}
a[l]='P';
a[r]='C';
l++;
r--;
k--;
}
for(ll i=0;i<n;i++)
{
if(a[i]=='C')
{
c++;
}
}
ll ans=0;
for(ll i=0;i<n;i++)
{
if(a[i]=='P')
{
ans+=p*c;
p++;
}
else
{
c--;
}
}
cout<<ans;
return 0;
}