백준 / A와 B / 12904번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: A와 B / 12904번 (골드 5단계)

문제 사이트: https://www.acmicpc.net/problem/12904

 

문제 설명

---

나의 풀이

def solution(s, t):
    t = list(t)  # 문자열을 리스트로 변환하여 수정 가능하게 만듦

    while len(t) > len(s):
        if t[-1] == 'A':
            t.pop()  # 마지막 문자 제거
        else:
            t.pop()  # 마지막 문자 제거
            t.reverse()  # 문자열 뒤집기

    return 1 if ''.join(t) == s else 0


def main():
    s = input().strip()  # 공백 제거
    t = input().strip()

    print(solution(s, t))


if __name__ == "__main__":
    main()

---

※ 알아야 할 것

초기 문자열에서 목표 문자열까지 도달하려면 경우의 수가 2^(len(t) - len(s))만큼 생깁니다. 그래서 목표 문자열에서 초기 문자열로 도달할 수 있는지 확인하는 방법이 적절합니다.

탑 다운 X -> 바텀 업 방식으로 사용하면 됩니다.