[BOJ 22412 // C++] ABC Gene

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

 

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

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

 

문자열 "ABC"에 주어진 규칙대로 변화를 1회 이상 주어 얻은 어떤 문자열을 S라 하자. 이 때, S의 이전 단계는 무엇인지 역추적할 수 있을까?

 

S의 부분문자열로 "ABC"가 존재하지 않는다면 어떤 변화로도 해당 문자열을 얻을 수 없을 것이다. 따라서 S는 부분문자열로 "ABC"를 적어도 하나 포함해야 한다. 한편, 모든 부분문자열 "ABC"는 이전 단계에서 바뀐 결과물이라는 점도 관찰할 수 있다. 이전 단계에서 어떤 문자를 ABC로 바꿔서 기존 문자와 연결된 새로운 "ABC"를 얻을 수는 없으며, 이전 단계에 있던 것이 그대로 오는 것도 불가능(어떤 연산을 해도 A나 B나 C가 있으므로 변화가 생김)하기 때문이다.

 

또한 이 "ABC"들이 어떤 문자였는지는 해당 문자열의 남은 다른 문자들 중 없는 문자가 되어야 한다는 점도 관찰하자. 이 때 남은 다른 문자가 0, 1, 3종류이면 불가능함을 확인하자.

 

위 관찰을 활용하여 주어진 문자열을 역추적해 문제를 해결하자.

 

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

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

string s, ss;

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

    cin >> s;

    while (s != "ABC") {
        bool chk = 0;
        ss.clear();
        for (auto &l:s) {
            ss += l;
            if (ss.length() > 2 && ss.substr(ss.length() - 3, 3) == "ABC") {
                ss.pop_back();
                ss.pop_back();
                ss.pop_back();
                ss += 'D';
                chk = 1;
            }
        }
        if (!chk) break;
        bool chkA = 0, chkB = 0, chkC = 0;
        for (auto &l:ss) {
            if (l == 'A') chkA = 1;
            else if (l == 'B') chkB = 1;
            else if (l == 'C') chkC = 1;
        }
        if (chkA && chkB && chkC) break;
        if (chkA && chkB) {
            for (auto &l:ss) {
                if (l == 'D') l = 'C';
            }
        }
        else if (chkB && chkC) {
            for (auto &l:ss) {
                if (l == 'D') l = 'A';
            }
        }
        else if (chkC && chkA) {
            for (auto &l:ss) {
                if (l == 'D') l = 'B';
            }
        }
        else break;
        swap(s, ss);
    }

    if (s == "ABC") cout << "Yes";
    else cout << "No";
}