[파이썬] 백준 12904 : A와 B (골드5)

[파이썬] 백준 12904 : A와 B (골드5)

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

---

풀이

방향성 생각

• start to end로 BFS처럼 진행하면 $2^1000$이라서 메모리 초과.
• 반대로 end to start로 진행하면, 선택지는 하나밖에 없음.
  • 마지막이 A이면 A 제거.
  • 마지막이 B이면 B 제거하고 뒤집기.
• 계속 문자열을 제거하면서 start 문자가 나오면 가능, 아니면 불가능.

 

---

전체코드

start = input()
end = input()

answer = 0
while True:

    # 문자열 둘이 같아졌으면 탈출
    if start == end:
        answer = 1
        break

    # end를 계속 제거했음에도 불구하고, start를 못찾은 경우 탈출
    if len(start) > len(end):
        answer = 0
        break

    # 마지막이 A이면 맨 뒤 제거
    if end[-1] == 'A':
        end = end[:-1]
    # 마지막이 B이면 맨 뒤 제거 후 뒤집기.
    else:
        end = end[:-1]
        end = end[::-1]
print(answer)

코멘트

• 비트로 바꿔서 하면 더 빠를지도?