주어진 문자열에서 ABC를 BCA로 최대 몇 번 바꿀 수 있는지 출력하는 문제.

Solution

생각보다 쉽지 않은데 몇 가지 특징을 써보자.

A, BC는 덩어리로 움직이고 나머지 문자열은 무시할 수 있다.
=> 나머지 문자열이 나오면 더 이상 변환이 불가능하다.
A, BC들이 적절히 만났을 때 모든 변환이 끝나면 A는 맨 뒤로 이동한다. (AABCBCBC => BCBCBCAA)
=> BC가 나오면 그 전의 A 개수만큼 변환 가능하다.

A 개수를 누적으로 카운트 해주면서 BC를 만나면 A 개수를 정답에 계속 더해나가면 된다.

Source Code

#include <iostream>
#include <string>
using namespace std;

int main() {
	string s;
	cin >> s;

	// dummy
	s += "F";

	long long ans = 0;
	long long aCount = 0;

	for (int i = 0; i < s.length(); i++)
	{
		if (s[i] == 'A')
		{
			aCount++;
		}
		else if (s.substr(i, 2) == "BC")
		{
			ans += aCount;
			i++;
		}
		else
		{
			aCount = 0;
		}
	}

	cout << ans << endl;
}

AGC_034_B - ABC

Problem link

Problem Summary

Solution

Source Code