이번 문제는 백트레킹을 통해 해결하였다. 처음에는 s에 두가지 연산을 계속해서 적용해보는 백트레킹을 구현하였다. 값은 정확하게 도출되었지만 시간초과가 발생하였다. 그래서 이번에는 t에 두가지 연산의 반대 연산을 계속해서 적용하는 백트레킹을 구현하였다. 이 경우에는 t의 가장 뒤의 문자가 A일 때만 1번 연산이 가능하고, t의 가장 앞의 문자가 B일 때만 2번 연산이 가능하였기 때문에 가짓수가 적어지는 것을 알 수 있었고, 문제가 해결되었다.

Code

s=str(input())
t=str(input())
answer=0
def reverse_chk(cur_t):
    global answer
    if len(cur_t)==len(s):
        if cur_t==s:
            answer=1
            print(answer)
            quit()
        return
    if cur_t[-1]=='A':
        reverse_chk(cur_t[:-1])
    if cur_t[0]=='B':
        reverse_chk(cur_t[::-1][:-1])
reverse_chk(t)
print(answer)