[Python] 백준 12919 - A와 B 2 문제 풀이

Overview

BOJ 12919번 A와 B 2 Python 문제 풀이
분류: Brute Force (완전탐색)

---

문제 페이지

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

---

풀이 코드 1 - 시간초과

from sys import stdin


def dfs(s: str, t: str) -> int:
    if len(s) == len(t):
        return [0, 1][s == t]

    op1 = dfs(s + 'A', t)
    op2 = dfs('B' + s[::-1], t)

    return op1 or op2


def main():
    S = stdin.readline().rstrip()
    T = stdin.readline().rstrip()
    print(dfs(S, T))


if __name__ == "__main__":
    main()

시간초과가 발생한 코드이다.
S 에서부터 2 가지 연산을 모두 사용해보며 T가 될 수 있는지 탐색한다.

---

풀이 코드 2

from sys import stdin


def dfs(s: str, t: str) -> int:
    if len(s) == len(t):
        return [0, 1][s == t]

    if t[-1] == 'B':
        if t[0] != 'B':
            return 0
        return dfs(s, t[:0:-1])

    else:
        if t[0] == 'A':
            return dfs(s, t[:-1])
        else:
            return dfs(s, t[:0:-1]) or dfs(s, t[:-1])


def main():
    S = stdin.readline().rstrip()
    T = stdin.readline().rstrip()
    print(dfs(S, T))


if __name__ == "__main__":
    main()

이전 코드와 달리 T에서부터 거꾸로 연산을 진행하며 S 가 될 수 있는지 탐색한다. 각 단계에서 사용 가능한 연산이 제한되기 때문에 경우의 수가 크게 줄어든다.