취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 27563번 문제인 Moo Operations이다.
문제는 아래 링크를 확인하자.

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

길이가 3 미만인 문자열은 어떻게 조작해도 세 글자의 문자열로 만들 수 없다. 길이가 3 이상인 문자열에 대해서 생각해보자.

먼저 주어진 문자열의 길이를 3으로 만들어야하므로 문자를 지우는 연산을 (문자열의 길이 - 3)회 해야함을 관찰하자. 또한 문자를 지우는 연산은 주어진 문자열의 맨 앞과 뒤에만 시행할 수 있으므로 남는 문자의 위치는 주어진 문자열의 연속한 세 문자 중 하나가 됨을 관찰하자. 따라서 문제의 답은 (문자열의 길이 - 3)과 (주어진 문자열의 길이 3의 부분문자열 중 하나를 "MOO"로 바꾸는 데에 필요한 연산 개수의 최솟값)의 합으로 구할 수 있다.

길이 3의 문자열의 가짓수는 8종류뿐이므로 각 종류에 대해 이를 "MOO"로 바꿀 수 있는지, 있다면 몇 회의 연산을 추가로 필요로 하는지를 미리 전처리하는 것은 어렵지 않다. 이를 이용해 문제를 해결해주자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int Q;
string s; int slen;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> Q;
	while (Q--) {
		cin >> s;
		slen = s.length();
		if (slen < 3) {
			cout << -1 << '\n';
			continue;
		}

		bool chk1 = 0, chk2 = 0, chk3 = 0;
		for (int i = 3; i <= slen; i++) {
			string tmp = s.substr(i - 3, 3);
			if (tmp == "MOO") chk3 = 1;
			else if (tmp == "MOM" || tmp == "OOO") chk2 = 1;
			else if (tmp == "OOM") chk1 = 1;
		}

		if (chk3) cout << slen - 3 << '\n';
		else if (chk2) cout << slen - 2 << '\n';
		else if (chk1) cout << slen - 1 << '\n';
		else cout << -1 << '\n';
	}
}