백준 12919. A와 B 2

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

S = input().rstrip()
T = input().rstrip()
res = 0

def dfs(word):
    global res

    if word == S:
        res = 1
        return

    if len(word) == 0:
        return

    if word[-1] == 'A':
        dfs(word[:-1])

    if word[0] == 'B':
        dfs(word[1:][::-1])

dfs(T)
print(res)

[체크포인트]

S->T로 변경 가능한지 검색보다

T->S로 가능한지로 해야 시간과 메모리 절약이 되면서 시간초과가 나지 않는다!

그러면 if 문 2개로 재귀함수를 돌리는데,

1. 맨 뒤가 'A'인지

2. 맨 앞이 'B'인지

이 두 가지를 탐색해야된다. 

예를 들면,

BABA -> BAB -> BA -> B (A추가->B추가하고 뒤집음->A추가)
BABA -> BAB -> BA -> A (B추가하고 뒤집음->B추가하고 뒤집음->A추가)

이렇게 S = 'A', T = 'BABA' 인 경우 두 가지 경우가 모두 나올 수 있기 때문이다!

이렇게 A에서 B로 만드는...이런 식인데 시간초과가 난다면 역으로 생각해보는 것이 중요한 것 같다.