취미로 코딩하기

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

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

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

같은 문자가 연속으로 등장("aa", "bb", cc")하는 경우 해당 부분을 문자열에서 지우더라도 문제의 답이 달라지지 않는다. 먼저 주어진 문자열 s에서 이러한 부분문자열을 지우자. 이 때, 문자열을 일부 지운 뒤 이어붙이는 과정에서 지우고자 하는 형태의 문자열이 다시 생길 수 있음에 유의하자. 만약 이렇게 얻은 문자열이 빈 문자열이라면 답은 "closed"가 된다.

현재 남은 문자열이 빈 문자열이 아니라 가정하자. 만약 이 문자열이 나타내는 곡선이 closed라면 해당 곡선 "내부"에서 팔각형을 하나 고를 수 있을 것이다. 그리고 다음과 같은 연산들을 적절하게 이용해 고른 팔각형을 문자열이 나타내는 곡선으로 변환할 수 있을 것이다(물론 문자열이 나타내는 곡선이 open이라면 불가능하다):

(1) "aa", "bb", "cc"의 삽입

(2) 부분문자열 "a"를 "bababab"로 변경 (과 같은 형태의 연산들)

(3) 부분문자열 "ab"를 "bababa"로 변경 (과 같은 형태의 연산들)

(4) 부분문자열 "aba"를 "babab"로 변경 (과 같은 형태의 연산들)

(5) 부분문자열 "abab"를 "baba"로 변경 (과 같은 형태의 연산들)

(6) 부분문자열 "ababa"를 "bab"로 변경 (과 같은 형태의 연산들)

(7) 부분문자열 "ababab"를 "ba"로 변경 (과 같은 형태의 연산들)

(8) 부분문자열 "abababa"를 "b"로 변경 (과 같은 형태의 연산들)

해당 변환과정은 내부의 팔각형을 주어진 곡선모양으로 "펼쳐나가는" 과정과 문자열 변환을 대응시켜 상상해보면 쉽게 이해할 수 있을 것이다.

따라서, 주어지는 문자열을 위의 규칙의 역과정만으로 변환해 빈 문자열로 만들 수 있는지를 확인하는 것으로 문제를 해결할 수 있다. "aa", "bb" 및 "cc"가 빈 문자열과 같다는 점을 잘 이용하면 직접 구현해 확인해야 할 경우의 수를 줄일 수 있으니 잘 생각해보자.

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

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

int T;
string S, s;

void func(string q) {
	for (auto& l : q) {
		s += l;
		int slen = s.length();
		if (s.length() > 1) {
			string ss = s.substr(slen - 2, 2);
			if (ss == "aa" || ss == "bb" || ss == "cc") {
				s = s.substr(0, slen - 2);
				continue;
			}
		}
		if (s.length() > 4) {
			string ss = s.substr(slen - 5, 5);
			if (ss == "ababa") {
				s = s.substr(0, slen - 5);
				func("bab");
			}
			else if (ss == "babab") {
				s = s.substr(0, slen - 5);
				func("aba");
			}
			else if (ss == "bcbcb") {
				s = s.substr(0, slen - 5);
				func("cbc");
			}
			else if (ss == "cbcbc") {
				s = s.substr(0, slen - 5);
				func("bcb");
			}
			else if (ss == "cacac") {
				s = s.substr(0, slen - 5);
				func("aca");
			}
			else if (ss == "acaca") {
				s = s.substr(0, slen - 5);
				func("cac");
			}
		}
	}
}

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

	cin >> T;
	while (T--) {
		cin >> S;
		s = "";

		func(S);

		if (s.length()) cout << "open\n";
		else cout << "closed\n";
	}
}