[백준] 12919번 A와 B 2 ★

💡문제접근

• [[백준] 12904번 A와 B]문제와 비슷하지만 두 문제는 서로 다른 문제였다.
• 거꾸로 거슬러 올라가는 방법을 이용해서 T를 S로 만들 수 있는지 여부를 따져 코드를 작성했다.

💡코드(메모리 : 31256KB, 시간 : 44ms)

import sys
input = sys.stdin.readline

def backtracking(N):
    global flag
    if len(S) == len(N):
        if S == N:
            flag = True
        return

    if N[-1] == "A":
        N.pop()
        backtracking(N)
        N.append("A")

    if N[0] == "B":
        N.reverse()
        N.pop()
        backtracking(N)
        N.append("B")
        N.reverse()

S = list(input().strip())
T = list(input().strip())
flag = False
backtracking(T)
if flag:
    print(1)
else:
    print(0)

💡소요시간 : 47m