[Boj] 백준 A와 B 2 12919(python)

문제링크 : https://www.acmicpc.net/problem/12919

BFS와 DFS를 하기에 앞서서, 제귀에 관한 문제를 풀어볼 필요가 있었음

제귀란 함수가 자기자신을 호출하는 것을 의미하며, 종료조건을 설정하지 않을 경우 무한루프에 빠지므로 주의 요망

이 문제는 문자열 S로 뒤에 ‘A’를 붙이거나, ‘B’를 붙인 후 뒤집는 것으로 문자열 T를 만들 수 있는지 판별하는 것이 목표

처음에는 S로 T로 만드는 것으로 시도해보았으나, 그 결과 15퍼 정도에서 시간초과가 발생

그래서 이후에는 T에서 마지막 문자가 ‘A’일 때 빼거나, 만약 첫 문자가 ‘B’일 경우 뒤집고 마지막 문자를 빼는 방법으로 접근함

다음부터는 큰 쪽에서 작은 쪽으로 만드는 방향으로 먼저 생각해야 시간을 절약할 수 있을 듯함.

import sys
sys.setrecursionlimit(10 ** 8)


def checkT(end):
    global answer
    if end == S:
        answer = 1
        return
    if len(end) <= len(S):
        return
    if end[-1] == 'A':
        checkT(end[:len(end)-1])
    if end[0] == 'B':
        tmp = end[::-1]
        checkT(tmp[:len(end)-1])
    return



S = input()
T = input()
answer = 0
checkT(T)
print(answer)