[백준] 12904번 A와 B 파이썬 풀이

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

12904번: A와 B

---

1. 풀이

• S에 말고 T에 집중하자

처음에는 S에서 T를 만들어 나가는 방식으로 접근했다. S 뒤에 A나 B가 붙는 모든 경우의 수를 고려하면, 그 수가 엄청나게 많아진다. 위 그림만 보아도, B 1글자에서 만들 수 있는 4글자 문자열은 2^(4 - 1) = 8개이다. 최악의 경우라면 S 길이가 1이고, T의 길이가 1,000일 때니까, 경우의 수는 무려 2^999개이다. 한편, 재귀 함수를 호출하는 횟수는 2^(T 길이 - S 길이 - 1) - 2이다. ... 절대 재귀 함수 (탑다운 방식)은 안 된다. 따라서 T에서 S를 만들어 나가는 것으로 방향을 잡자.

 

 

• T의 마지막 문자부터 차례대로 제거해 나가자

S에서 T를 만들어 나갈 때, A를 붙이든 B를 붙이든 무조건 마지막에 추가된다. 따라서 반대로 T에서 마지막 글자를 계속 제거해 나가면 처음 시작 문자열인 S를 구할 수 있을 것이다.

만약 입력한 S 문자열 길이만큼 T의 마지막 문자를 제거했는데도 S와 T가 같지 않다면, 그건 S로부터 T를 만들 수 없다는 의미이다.

 

 

 

 

2. 정답 코드

def solution(s, t):
    for _ in range(len(t) - len(s)):
        if t[-1] == 'A':
            t = t[:-1]
        else:
            t = t[:-1]
            t = t[::-1]

    return 1 if s == t else 0


S = input()
T = input()

print(solution(S, T))