백준 12904번 - A와 B

A와 B 문제 바로 가기

풀이 날짜: 2026-01-24

baekjoon 알고리즘 문제 풀이

풀이 코드


import sys
input = sys.stdin.readline

s = input().strip()
t = input().strip()

while len(t) > len(s):
    if t[-1] == 'A':
        t = t[:-1]
    else:
        t = t[:-1]
        t = t[::-1]
print(1 if t==s else 0)

print(count)

문제 핵심 요약:

12904번 문제는 문자열 S에서 T를 만드는 문제처럼 보이지만, 이 방향으로 생각하면 매 단계마다 선택지가 두 개(A 추가 / B 추가 후 뒤집기)로 갈라져 경우의 수가 폭발한다. 따라서 단순한 탐색이나 그리디로는 접근하기 어렵다. 이 문제의 핵심은 정방향(S → T)이 아니라 역방향(T → S)으로 생각해야 한다는 점이다.

역방향으로 생각

문자열의 마지막 문자가 A라면, 이는 이전 단계에서 A를 붙였다는 의미이므로 단순히 A를 제거하면 된다.
문자열의 마지막 문자가 B라면, 이는 B를 붙이고 뒤집은 결과이므로 B를 제거한 뒤 문자열을 다시 뒤집으면 이전 상태로 돌아갈 수 있다.

헷갈렸던 것 정리

문자열 슬라이싱