[백준/파이썬] 12919번 A와 B 2

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

12919번: A와 B 2

A와 B 1번 문제에 이어서 2번 문제이다.

 

A와 B 1번 문제는 while문을 이용해 T에서부터 S를 만들어 나갈 수 있었지만, 2번 문제 같은 경우 while 문을 이용하기엔 다양한 경우의 수가 존재해서 재귀 + 브루트 포스를 이용해 풀었다.

import sys
#sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def dfs(s,t):
    if s==t:
        return 1
    
    if len(t)<=len(s):
        return 0
    
    ans = 0
    if t[-1] == 'A': # 마지막이 A면 그냥 제거
        ans = dfs(s,t[:-1])
    if ans == 1:
        return 1

    if t[0]=='B': # 처음이 B면 reverse 후 제거
        ans = dfs(s,t[::-1][:-1])
        
    return ans

if __name__ == "__main__":
    S = list(input().rstrip())
    T = list(input().rstrip())
 
    print(dfs(S,T))