[BOJ 12904, Python 3] A와 B

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

12904번: A와 B

 

풀이

관점을 바꿔서 T를 S로 만들면 됩니다.

왜냐하면 S에서 T로 만드는 경우에는 오른쪽에는 A를, 왼쪽에는 B를 추가해야하고, 어떤 기준으로 A와 B를 추가해야하는지 알 길이 없습니다. 그렇다고 모든 경우의 수를 하기에는 S = 1, T = 1000이면 실제로는 이것보다 적겠지만 대충 2^999가지의 경우의 수를 확인해야해서 시간내에 풀 수 없습니다.

하지만 T에서 S로 만드는 경우에는

- 문자열 뒤에 A를 삭제한다

-문자열 뒤에 B를 삭제하고 문자열을 뒤집는다.

라서 무조건 오른쪽 문자를 없애는 것이므로 뒤의 문자열이 A인지 B인지 확인하면서 풀 수 있습니다.

 

 

코드

s = [*input()]
t = [*input()]
while len(s) != len(t):
    if t[-1] == 'A': t.pop()
    else: t.pop(); t = t[::-1]
flag = True
for i in range(len(s)):
    if t[i] != s[i]: flag = False
print([0, 1][flag])