[백준/C++] PPC 만들기 (No. 31778)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 문제의 규칙만 빠르게 파악하면 쉽게 풀 수 있는 문제다.

 

PPC 부분 문자열을 찾는 것이므로 PPC 부분문자열의 최대 개수를 찾으려면 뒤에있는 P와 앞에 있는 C를 바꾸면 된다.

 

왜냐하면 C문자열이 등장했을 때, 앞에 나왔던 P의 등장 횟수에 의해서만 부분 문자열의 개수가 정해지기 때문이다.

 

예를 들어 CCCCCCCCCCCCCCPPC 와 같은 경우 PPC를 만드는 경우 앞에 C문자열이 몇 개가 나오던 현재 C문자열로 만들 수 있는 PPC 문자열에 영향을 끼치지 않기 때문이다.

 

이때, 빠르게 계산하기 위한 아이디어는 앞에서부터 C를 찾았고 뒤에서부터 P를 찾아서 바꿨으므로 그 위치를 저장해 변환 연산을 할지 이전 위치부터 시작하면 된다.

 

그림을 통해 더 쉽게 생각해보자.

위 그림처럼 P와 C의 위치를 바꾼 이후에는 그 다음 위치부터 탐색을 하면 위치를 바꾸는데 O(N)의 시간으로 문제를 해결할 수 있다.

 

이후 PPC의 개수를 구하는 방법은 C가 나올 때 마다 [ 이전에 등장한 P의 개수*(P의 개수-1)/2]를 더해주면 된다.

 

 

 

 

[아이디어 정리]

1. PPC 부분문자열의 수를 최대로 만들기 위해서는 뒤에서부터 P를 찾고 앞에서부터 C를 찾아 K번 위치를 변경해주면 된다.
2. 이때, 이전에 탐색했던 위치를 기록해 연산을 빠르게 한다.
3. 위치 변환이 끝난 이후에는 C가 나올때 마다 [ 이전에 등장한 P의 개수*(P의 개수-1)/2 ]를 더한다.
4. 최종 결과값을 출력한다.

 

 

Code

 

 

 

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	long long N,K;
	cin >> N >> K;
	vector<char> S(N);
	for (int i=0; i<N; i++)
	{
		cin >> S[i];
	}
	long long st = 0, ed = N - 1;
	char tmp;
	bool fS = false, fE = false;
	while(K>0)
	{
		fS = false;
		fE = false;
		for (int i= st; i<N; i++)
		{
			if (S[i]=='C')
			{
				st = i;
				fS = true;
				break;
			}
		}
		for (int j=ed; j>=0; j--)
		{
			if (S[j]=='P')
			{
				ed = j;
				fE = true;
				break;
			}
		}

		if (fS&&fE)
		{
			if (st < ed)
			{
				K--;
				S[st] = 'P';
				S[ed] = 'C';
			}
			else {
				break;
			}
		}
		else {
			break;
		}
	}
	long long cntP = 0;
	long long plusF = 0;
	long long ans = 0;
	for (int i = 0; i < N; i++)
	{

		if (S[i] == 'P')
		{
			cntP++;
			plusF += cntP - 1;
		}
		else
		{
			ans += plusF;	
		}
	}
	cout << ans;
	return 0;
}

 

---

 

문제 자체는 어렵지 않아 빠르게 생각했는데, P와 C의 위치를 바꿔줄 때 P와 C가 등장하지 않아서 생기는 반례를 고려하지 않아서 계속 틀렸다;;

 

거의 40분 동안 맞왜틀만 반복했네... ㅠㅠ

 

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