[백준] 12919 A와 B 2

A와 B의 규칙을 잘 생각해보자

우리는 S->T 가 아닌 뒤집어서 T->S로 문제를 풀어본다!

 

1) 맨 뒤에 A를 붙인다

2) 맨 뒤에 B를 붙이고 뒤집기 => 뒤집고 앞에 B 붙이기

 

 

그럼 문제를 풀기 위해 나올 수 있는 상황 4가지를 생각해보자

 

 

1. A ~ A => 1번경우 가능

2. A ~ B => 불가능

3. B ~ A => 1,2 번 가능

4. B ~ B => 2번가능

 

4가지를 그대로 코딩해주면 시간안에 충분히 나온다!

 

 

 

소스코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string s, t;
 
bool solve(string f) {
    if (f.length() < s.length()) return false;
    if (f.length() == s.length()) return (s == f);
    bool ret = false;
    char s = f[0], e = f.back();
    int len = f.length();
    if (s == 'A') {
        if (e == 'A') ret |= solve(f.substr(0, len - 1));
        else return false;
    }
    else {
        if (e == 'A') ret |= solve(f.substr(0, len - 1));
        reverse(f.begin(), f.end());
        f.pop_back();
        ret |= solve(f);
    }
    return ret;
}
int main() {
    cin >> s >> t;
    printf("%d\n", solve(t));
}