※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※
이번에 볼 문제는 백준 4139번 문제인 Octagons이다.
문제는 아래 링크를 확인하자.
https://www.acmicpc.net/problem/4139
4139번: Octagons
Below is a picture of an infinite hyperbolic tessellation of octagons. If we think of this as a graph of vertices (of degree three), then there exists an isomorphism of the graph which maps any vertex x onto any other vertex y. Every edge is given a label
www.acmicpc.net
같은 문자가 연속으로 등장("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";
}
}'BOJ' 카테고리의 다른 글
| [BOJ 14170 // C++] Counting Haybales (0) | 2023.10.18 |
|---|---|
| [BOJ 4138 // C++] Paper Route (1) | 2023.10.17 |
| [BOJ 8310 // C++] Riddle (0) | 2023.10.15 |
| [BOJ 18259 // C++] Greedy Pie Eaters (0) | 2023.10.14 |
| [BOJ 18260 // C++] Bessie's Snow Cow (0) | 2023.10.13 |