[백준 12904][파이썬][그리디] A와 B

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

12904번: A와 B

 

두 가지 연산을 통해 S에서 T로 바꿀 수 있는지 판단하는 문제이다.

 

처음에는 S에서 T로 바꾸는 방식으로 시도를 했는데 굉장히 까다로웠다.

 

S에서 T로 바꾸는 방식은 하나의 단계마다 여러 가지 경우의 수가 존재하기 때문에 신경써야하는 부분이 많다.

 

그런데 T에서 S로 바꾸는 방식은 하나의 단계마다 단 하나의 경우의 수만 존재한다.

 

길이가 4인 문자열의 마지막 단어는 무조건 'A' 아니면 'B'인데

 

만약 마지막 단어가 'A'라면 길이가 3인 특정 문자열의 뒤에 'A'를 붙였을 것이다.

 

만약 마지막 단어가 'A'라면 길이가 3인 특정 문자열의 뒤집어서 뒤에 'B'를 붙였을 것이다.

 

백준 11501번 문제처럼 거꾸로 생각해서 푸는 문제이다.

https://growth-coder.tistory.com/225

[백준 11501][파이썬] 주식 (그리디, 재귀)

 

거꾸로 생각해보는 습관을 기르자.

 

import sys
input=sys.stdin.readline
s=input().rstrip()
t=input().rstrip()
while(len(t)>len(s)): # t의 길이가 s와 같아질 때까지
    if t[-1]=='A': # 마지막 A면 빼버림
        t=t[:-1]
    else: # 마지막 B면 빼고 뒤집음
        t=t[:-1]
        t=t[::-1]
print(1 if s==t else 0)