A와 B

첫번째 풀이

answer = []
def addA(word):
    return word + "A"

def flipAddB(word):
    return word[::-1] + "B"

def simulate(start, target):
    if start == target:
        answer.append(start)
        return
    if len(start) >= len(target):
        return
    # 백트래킹
    simulate(addA(start), target)
    simulate(flipAddB(start), target)

S = input()
T = input()
simulate(S, T)

if answer:
    print(1)
else:
    print(0)

# ---
# 시간초과

두번째 풀이

# target -> start 방향으로 체크
def simulate(start, target):
    while len(target) != len(start):
        if target[-1] == "A":
            target = target[:-1]
        elif target[-1] == "B":
            target = target[:-1][::-1]
    return start, target


S = input()
T = input()

s, t = simulate(S, T)

if s == t:
    print(1)
else:
    print(0)

G5

주어진 2가지 변환조건으로
문자열 S -> 문자열 T로 만들 수 있는지를 판단하는 문제였다.

처음에는 백트래킹으로 풀었는데 시간초과 가 났다. 아무래도 경우의 수가 너무 많았던 것 같았다.

그래서 역방향으로 목표 문자열에서 차감해서 처음 문자열이 되는지를 체크하는게 훨씬 빠를 것 같았다.

여기서는 굳이 재귀를 쓸 필요가 없었는데, 길이 비교 while문을 돌려서 마지막에 문자열 비교만 해주면 풀리는 알고보면 간단한 문제였다.

하지만 역으로 갈 생각을 할 수 있느냐가 이 문제가 어려운 이유가 되겠다.

출처: https://www.acmicpc.net/problem/12904